c - 图的初始化和使用

Question

我正在尝试实现一个图表来存储文本文件中的数据列表，如下所示:

0,1 (node 0 links to 1)
0,2 (node 0 links to 2)
1,2 (node 1 links to 2)
2,1 (node 2 links to 1)

无论如何，当涉及到定义结构时，我遇到了麻烦。我在使用矩阵或相邻列表之间左右为难，但我想我会使用列表，我只是不确定如何定义结构。我应该使用可变大小的数组、链表还是其他东西？哪种方式最简单？

struct grph{

};

struct node{

    //ID of the node
    int id;

};

其次，我如何将数据存储到这个图中，这是我遇到的最麻烦的地方。本质上，我认为它会像链表一样简单，您只需在末尾不断添加一个节点。这里的区别在于每个节点可以指向许多不同的节点或根本不指向任何节点。如何将图形结构与所有链接的节点结构链接起来？

例如，当使用链表时，我将如何存储上例中节点 0 连接到的节点？我知道您使用矩阵或列表/数组，但由于在 C 中缺少此类实现的示例，我感到非常困惑。我发现的任何示例都比以前更糟。

Answer 1

这只是一个例子:

struct node{
        int id; 
        struct node **out;
        int num_out;
        /* optional: if you want doubly links */
        struct node **in;
        int num_in;
};

/* quick access to a node given an id */
struct node *node_list;

/* connect 'from' to 'to' */
void link(struct node *graph, int from, int to) {
        struct node *nfrom = &node_list[from], 
                    *nto   = &node_list[to];
        nfrom->num_out++;
        nfrom->out = realloc(nfrom->out, 
             sizeof(struct node*) * nfrom->num_out);
        nfrom->out[num_out-1] = nto;
        /* also do similar to nto->in if you want doubly links */
}