C 中用于无向（未加权）图的邻接表

Question

这是我的代码：

#define V 5

typedef struct edge* link;

//structure for reprenting edges
typedef struct edge{
    int dst;        //number of destination node
    //int weight;   //for weigthed graphs
    link next;      //link to next edge
} edge_t;

link new_edge(int dst, link next) {
    link edge = (link) malloc(sizeof(edge_t));

    edge->dst = dst;
    edge->next = next;
    return edge;
}

int main() {

    link edge;
    link adj[V];
    //the array contains V pointers to lists of edges
    //each list for each node of my graph

    int i;
    int j;

    //all lists are empty at beginning
    for (i = 0; i < V; i ++) {
        adj[i] = NULL;
    }

    printf("input the edges:\n");
    
    while (scanf("%d %d", &i, &j) == 2) {
        adj[i] = new_edge(j, adj[i]);
        //in the list for node i
        //put the edge to node j
        adj[j] = new_edge(i, adj[j]); //if it is undirect
        //in the list for node j
        //put the edge to node i
    }
    
    printf("adjacency list is: \n");
    //cycle over the nodes
    for (i=0; i<V; i++) {
        if (adj[i] == NULL) {
            printf("%d is null list\n", i);
        }
        //print all the edges for that node
        for (edge = adj[i]; edge != NULL; edge = edge -> next) {
            printf("edge %d -> %d\n", i, edge->dst);
        }
    }
}

输入：
0 1
0 2
1 3
停止
输出：
邻接表是：
边 0 -> 2
边 0 -> 1
边 1 -> 3
边 1 -> 0
边 2 -> 0
边 3 -> 1
4 是空列表

这张图显示了我的new_edge函数是如何工作的，蓝色区域（图中）正在改变，所以我可以遍历列表，所以我的问题是为什么蓝色area 等于 NULL？，因为它指向列表中的最后一项，我认为它不会为 NULL（P.S 我在遍历列表以打印时验证它为 null）。

Answer 1

adj的元素是指向节点的指针，而不是节点。另一方面，节点中的next指向的是节点，而不是指向节点的指针。因此，next 不会指向 adj.

的元素

这就是您的代码的实际工作方式：

如您所见，指针没有回环，您的蓝色区域（添加了节点的 adj 的元素）不等于 NULL。

C 中用于无向（未加权）图的邻接表

Adjacency List in C for undirected (unweighted) graph

c

linked-list

graph-algorithm

undirected-graph