c 显示图的邻接表

Question

我已经编写了基于小型 c 图的实现的代码，并相应地列出了图顶点的邻接表。我上面的代码是：

#include<stdio.h>
#include<stdlib.h>
struct node {
    int info;
    struct node* next;
}* z, *adjv[50], *t;
void insert() {
    int j, v, e, c, d, i;
    z = (struct node*)malloc(sizeof(struct node));
    z->next = z;
    scanf("%d%d", &v, &e);
    for (j = 1; j <= v; j++) {
        adjv[j] = z;
    }
    for (j = 1; j <= e; j++) {
        scanf("%d%d", &c, &d);
        t = (struct node*)malloc(sizeof(struct node));
        t->info = c;
        t->next = adjv[d];
        adjv[d] = t;
        t = (struct node*)malloc(sizeof(struct node));
        t->info = d;
        t->next = adjv[c];
        adjv[c] = t;
    }
    for (i = 1; i <= e; i++) {

        while (adjv[i] != z) {
            printf("%d", adjv[i]->info);
            adjv[i] = adjv[i]->next;
        }
    }
}
int main() {
    insert();
    return 0;
}

当我为它提供顶点 =4 edges=2 和边作为 (1,2) (3,4) 时，它不会将其显示为断开连接的图，因为邻接列表仅显示 1 和 2 的值。请帮助我纠正这个问题，以便显示正确的邻接表

Answer 1

您需要更好地构建数据。例如，目前，边由 struct node 表示，节点本身由指向 struct node.

的指针数组表示

在您的代码中，adjv[i] 是顶点 i 的邻接列表的头部，但是您的代码循环遍历了边数。你有 4 个顶点和 2 条边，所以你错过了与顶点 3 和 4 的连接。

一个更正的（更冗长的）打印循环将循环到顶点数：

for (i = 1; i <= v; i++) {
    while (adjv[i] != z) {
        printf("%d -> %d\n", i, adjv[i]->info);
        adjv[i] = adjv[i]->next;
    }
}

也就是说，请考虑通过以下方式使您的代码更具可读性和 C 风格：

使您的索引从零开始；
使用NULL指针作为链表的标记值；
为顶点和边提供不同的结构，因为它们代表不同的事物并且通常也需要不同的数据；
始终使用 node 或 vertex 之一，因为它们本质上是相同的东西，但在您的代码中应该有一个统一的名称，以便您可以快速了解正在发生的事情。

c 显示图的邻接表

c display adjacency list of graph

c

graph-algorithm