Графики с использованием списка смежности строк

Question

Я знаю, как представить целочисленный граф, используя список смежности. Однако со строкой это немного сложно. Я пытаюсь создать граф друзей. Где источник находится в индексе массива указателей. Затем добавляются друзья источника с использованием связанного списка, например хэширования. Теперь я создал массив указателей, в отличие от целочисленной программы, где я использую индекс в качестве значения графика, я не могу сделать это со списком строк.

Массив указателей хранит начальную строку

Пожалуйста, просмотрите его, и любое решение будет замечательно

// A C Program to demonstrate adjacency list 
// representation of graphs
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include  <string.h>
#include <string>

#define maxNode 4
int i;
int z;
typedef struct Node
{
    char vertexString[10];
    struct Node *next;
}Node;

Node *dest, *tmp;
typedef struct List
{
    Node*head;
    char vertexS[10];
    struct Node *next;
}List;

List*adjlist[maxNode] = { 0 };

void addNode(const char s[10], const char d[10]);
void printList();

int main()
{
        int i;
        for (i = 0; i < maxNode; i++)
        {
            adjlist[i] = (List *)malloc(sizeof(List));
            adjlist[i]->head = NULL;
        }
        addNode("Alam", "Shaib");
        addNode("ZEE", "PEE");
        addNode("ALOO", ",ALOO");

        printList();
        _getch();
}


void addNode(const char s[10],const char d[10])
{
        for (i = 0; i < 4;i++);
        {
            if (adjlist[i]->vertexS == s)
            {
                dest = (Node *)malloc(sizeof(Node));

                for (int j = 0; j < 10; j++)
                {
                    dest->vertexString[j] = d[j];
                }
                dest->next = NULL;

                tmp = adjlist[i]->head;
                while (tmp->next != NULL)
                    tmp = tmp->next;
                tmp->next = dest;
            }
        }

        for (z = 0; z < 4; z++);
        {
            if (adjlist[z] == 0)
            {
                dest = (Node *)malloc(sizeof(Node));
                for (int L = 0; L < 10; L++)
                {
                    dest->vertexString[L] = d[L];
                }
                dest->next = NULL;

                tmp = adjlist[z]->head;
                while (tmp->next != NULL)
                    tmp = tmp->next;
                tmp->next = dest;
            }
        }
    }

    void printList()
    {
        int i;
        for (i = 0; i < maxNode; i++)
        {
            Node *p;
            p = adjlist[i]->head;
            printf("Adjency list for vertex %s\n", adjlist[i]->vertexS);
            p = p->next;
            while (p)
            {
                printf("%s",p->vertexString);
                p = p->next;
            }

            printf("\n");
        }
    }

Answer 1

Вместо того, чтобы дублировать данные в вашем списке смежности, просто включите ссылки (индексы или указатели массива) на структуры, описывающие узлы.

Например, скажем, вы описываете свои узлы, используя связанный список, скажем,

typedef  struct node_list  node_list;
struct node_list {
    struct node_list *next;
    size_t            len;
    size_t            flag; /* Not usually needed, but sometimes useful */
    char              data[]; /* C99 flexible array member */
};

Чтобы найти существующий узел или добавить новый узел, вы можете использовать

node_list *node_list_node(node_list **rootptr, const char *name)
{
    const size_t  namelen = (name) ? strlen(name) : 0;
    node_list   **prev = rootptr, *curr;

    if (!rootptr)
        return NULL;  /* Error: No reference to node list root! */
    if (namelen < 1)
        return NULL;  /* Error: Empty name! */ 

    while ((curr = *prev))
        if (curr->len == namelen && !memcmp(curr->data, name, namelen))
            return curr;
        else
            prev = &(curr->next);

    curr = malloc(sizeof (node_list) + name_len + 1);        
    if (!curr)
        return NULL; /* Not enough memory */

    curr->next = NULL;
    curr->len  = namelen;
    memcpy(curr->data, name, namelen + 1);

    *prev = curr;

    return curr;
}

Затем вы можете определить ребра графа как другой связанный список, скажем,

typedef  struct adjacency_list  adjacency_list;
struct adjacency_list {
    struct adjacency_list  *next;
    struct node_list       *edge_from;
    struct node_list       *edge_to;
};

так, чтобы добавить ребро (без проверки на дубликаты) так же просто, как

adjacency_list *add_edge(node_list **node, adjacency_list **edge,
                         const char *from, const char *to)
{
    node_list      *node_from, *node_to;
    adjacency_list *newedge;

    if (!node || !edge || !from || !*from || !to || !*to)
        return NULL;

    node_from = node_list_node(node, from);
    node_to   = node_list_node(node, to);
    if (!node_from || !node_to)
        return NULL;

    newedge = malloc(sizeof (adjacency_list));
    if (!newedge)
        return NULL;

    newedge->edge_from = node_from;
    newedge->edge_to   = node_to;

    /* Prepend to the existing adjacency list. */
    newedge->next = *edge;
    *edge = newedge;

    return newedge;
}

Конечно, вы должны позаботиться о том, чтобы не перераспределять или освобождать node_list, если на него ссылается какой-либо объект adjacency_list, потому что перераспределение может переместить объект. (Опять же, вы можете настроить объекты adjacency_list, проверив их все, но если вы думаете, что можете это сделать, обычно лучше использовать массив указателей, а не связанных списков, и использовать индекс массива вместо указателя сам ссылаться на каждый узел.)

Если вы хотите вывести (под) граф, описанный связанным списком adjacency_list, в формате Graphviz Dot, но вывести только те узлы, которые включены в список, в элемент node_list входит элемент flag в удобной Например:

void fgraph(FILE *out, adjacency_list *edges)
{
    adjacency_list *curredge;

    if (!out)
        return;

    /* First, clear the 'flag' field in all referred to nodes.
       (We actually only need one bit, though.) */
    for (curredge = edges; curredge != NULL; curredge = curredge->next) {
         curredge->edge_from->flag = 0;
         curredge->edge_to->flag = 0;
    }

    /* Print a directed graph DOT preamble. */
    fprintf(out, "digraph {\n");

    /* Print each referred to node, but only once. */
    for (curredge = edges; curredge != NULL; curredge = curredge->next) {
        if (!curredge->edge_from->flag) {
            node_list *currnode = curredge->edge_from;

            currnode->flag = 1;
            fprintf(out, "    \"%p\" [ label=\"%s\" ];\n",
                         (void *)currnode, currnode->data);
        }
        if (!curredge->edge_to->flag) {
            node_list *currnode = curredge->edge_to;

            currnode->flag = 1;
            fprintf(out, "    \"%p\" [ label=\"%s\" ];\n",
                         (void *)currnode, currnode->data);
        }
    }

    /* Print each edge in the (sub)graph. */
    for (curredge = edges; curredge != NULL; curredge = curredge->next) {
        fprintf(out, "    \"%p\" -> \"%p\";\n",
                     (void *)(curredge->edge_from),
                     (void *)(curredge->edge_to));
    }

    /* Done. */
    fprintf(out, "}\n");
}

Затем вы можете использовать инструменты Graphviz, например dot, twopi или circo, чтобы создать изображение графика.