初始化和图形

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 */ 
} 

Answer 2

这似乎也挺喜欢我的工作，社交网络...... 你可以定义节点和链接seperately。在C语言中，你可以定义为：

struct graph_node{ 
    int id; 
    struct node_following *following; 
    struct graph_node *next_node; 
} 

struct node_following{ 
    int id; 
    struct node_following *next_node; 
} 

为了您的例子中，结果是： 根 - > NODE0 - >节点1 - >节点2

根的内容可能是：ID = -1 ;下列= NULL; next_node = node0

node0的内容可能是：id = 0; next_node = node1;以下指向node_following的列表： 以下 - > {1，下一个节点的地址} - > {2，NULL}

node1的内容可能是：id = 1; next_node = node2;以下指向node_following的列表： 以下 - > {2，NULL}

node2的内容可能是：id = 2; next_node = NULL;以下指向node_following列表： 以下 - > {1，NULL}

本质上，它是关于如何存储二维矩阵的一个问题。如果矩阵稀疏，请使用链接列表。否则，位图是更好的解决方案。

Answer 3

在回答第一个问题：adjacency矩阵vs邻接列表？如果你期望你的图是密集的，即大多数节点与大多数其他节点相邻，那么去矩阵，因为大多数操作在矩阵上更容易。如果你真的需要一个传递闭包，那么矩阵可能也会更好，因为它们往往是密集的。否则，邻接列表更快更小。

的图表将如下所示：

typedef struct node * node_p; 
typedef struct edge * edge_p; 

typedef struct edge 
{  node_p source, target; 
     /* Add any data in the edges */ 
} edge; 

typedef struct node 
{  edge_p * pred, * succ; 
     node_p next; 
     /* Add any data in the nodes */ 
} node; 

typedef struct graph 
{  node_p N; 
} graph; 

的的N场将使用的node的next场链接列表开始图的节点的链接列表。 pred和succ可以是使用malloc和realloc为图中的后继和前驱边（指针到边和NULL终止的数组）分配的阵列。尽管保留后继者和前辈看起来可能是多余的，但你会发现大多数图算法都能够双向运行。将边缘点的source和target字段指向节点。如果您不希望在边缘存储数据，则可以让pred和succ阵列直接指向节点并忘记edge类型。

不要在的N上尝试使用realloc，因为节点的所有地址都可能发生变化，这些在地图的其余部分都会大量使用。

P.S：我个人比较喜欢圆形链表在NULL收盘链表，因为代码大多数，如果不是全部，操作要简单得多。在这种情况下，将包含（虚拟）node而不是指针。

Answer 4

你可以做这样的事情：

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 

typedef struct 
{ 
    void* pElements; 
    size_t ElementSize; 
    size_t Count; // how many elements exist 
    size_t TotalCount; // for how many elements space allocated 
} tArray; 

void ArrayInit(tArray* pArray, size_t ElementSize) 
{ 
    pArray->pElements = NULL; 
    pArray->ElementSize = ElementSize; 
    pArray->TotalCount = pArray->Count = 0; 
} 

void ArrayDestroy(tArray* pArray) 
{ 
    free(pArray->pElements); 
    ArrayInit(pArray, 0); 
} 

int ArrayGrowByOne(tArray* pArray) 
{ 
    if (pArray->Count == pArray->TotalCount) // used up all allocated space 
    { 
    size_t newTotalCount, newTotalSize; 
    void* p; 

    if (pArray->TotalCount == 0) 
    { 
     newTotalCount = 1; 
    } 
    else 
    { 
     newTotalCount = 2 * pArray->TotalCount; // double the allocated count 
     if (newTotalCount/2 != pArray->TotalCount) // count overflow 
     return 0; 
    } 

    newTotalSize = newTotalCount * pArray->ElementSize; 
    if (newTotalSize/pArray->ElementSize != newTotalCount) // size overflow 
     return 0; 

    p = realloc(pArray->pElements, newTotalSize); 
    if (p == NULL) // out of memory 
     return 0; 

    pArray->pElements = p; 
    pArray->TotalCount = newTotalCount; 
    } 

    pArray->Count++; 
    return 1; 
} 

int ArrayInsertElement(tArray* pArray, size_t pos, void* pElement) 
{ 
    if (pos > pArray->Count) // bad position 
    return 0; 

    if (!ArrayGrowByOne(pArray)) // couldn't grow 
    return 0; 

    if (pos < pArray->Count - 1) 
    memmove((char*)pArray->pElements + (pos + 1) * pArray->ElementSize, 
      (char*)pArray->pElements + pos * pArray->ElementSize, 
      (pArray->Count - 1 - pos) * pArray->ElementSize); 

    memcpy((char*)pArray->pElements + pos * pArray->ElementSize, 
     pElement, 
     pArray->ElementSize); 

    return 1; 
} 

typedef struct 
{ 
    int Id; 

    int Data; 

    tArray LinksTo; // links from this node to other nodes (array of Id's) 
    tArray LinksFrom; // back links from other nodes to this node (array of Id's) 
} tNode; 

typedef struct 
{ 
    tArray Nodes; 
} tGraph; 

void GraphInit(tGraph* pGraph) 
{ 
    ArrayInit(&pGraph->Nodes, sizeof(tNode)); 
} 

void GraphPrintNodes(tGraph* pGraph) 
{ 
    size_t i, j; 

    if (pGraph->Nodes.Count == 0) 
    { 
    printf("Empty graph.\n"); 
    } 

    for (i = 0; i < pGraph->Nodes.Count; i++) 
    { 
    tNode* pNode = (tNode*)pGraph->Nodes.pElements + i; 

    printf("Node %d:\n Data: %d\n", pNode->Id, pNode->Data); 

    if (pNode->LinksTo.Count) 
    { 
     printf(" Links to:\n"); 

     for (j = 0; j < pNode->LinksTo.Count; j++) 
     { 
     int* p = (int*)pNode->LinksTo.pElements + j; 
     printf(" Node %d\n", *p); 
     } 
    } 
    } 
} 

void GraphDestroy(tGraph* pGraph) 
{ 
    size_t i; 

    for (i = 0; i < pGraph->Nodes.Count; i++) 
    { 
    tNode* pNode = (tNode*)pGraph->Nodes.pElements + i; 
    ArrayDestroy(&pNode->LinksTo); 
    ArrayDestroy(&pNode->LinksFrom); 
    } 

    ArrayDestroy(&pGraph->Nodes); 
} 

int NodeIdComparator(const void* p1, const void* p2) 
{ 
    const tNode* pa = p1; 
    const tNode* pb = p2; 

    if (pa->Id < pb->Id) 
    return -1; 
    if (pa->Id > pb->Id) 
    return 1; 
    return 0; 
} 

int IntComparator(const void* p1, const void* p2) 
{ 
    const int* pa = p1; 
    const int* pb = p2; 

    if (*pa < *pb) 
    return -1; 
    if (*pa > *pb) 
    return 1; 
    return 0; 
} 

size_t GraphFindNodeIndexById(tGraph* pGraph, int Id) 
{ 
    tNode* pNode = bsearch(&Id, 
         pGraph->Nodes.pElements, 
         pGraph->Nodes.Count, 
         pGraph->Nodes.ElementSize, 
         &NodeIdComparator); 

    if (pNode == NULL) 
    return (size_t)-1; 

    return pNode - (tNode*)pGraph->Nodes.pElements; 
} 

int GraphInsertNode(tGraph* pGraph, int Id, int Data) 
{ 
    size_t idx = GraphFindNodeIndexById(pGraph, Id); 
    tNode node; 

    if (idx != (size_t)-1) // node with this Id already exist 
    return 0; 

    node.Id = Id; 
    node.Data = Data; 
    ArrayInit(&node.LinksTo, sizeof(int)); 
    ArrayInit(&node.LinksFrom, sizeof(int)); 

    if (!ArrayInsertElement(&pGraph->Nodes, pGraph->Nodes.Count, &node)) 
    return 0; 

    qsort(pGraph->Nodes.pElements, 
     pGraph->Nodes.Count, 
     pGraph->Nodes.ElementSize, 
     &NodeIdComparator); // maintain order for binary search 

    return 1; 
} 

int GraphLinkNodes(tGraph* pGraph, int IdFrom, int IdTo) 
{ 
    size_t idxFrom = GraphFindNodeIndexById(pGraph, IdFrom); 
    size_t idxTo = GraphFindNodeIndexById(pGraph, IdTo); 
    tNode *pFrom, *pTo; 

    if (idxFrom == (size_t)-1 || idxTo == (size_t)-1) // one or both nodes don't exist 
    return 0; 

    pFrom = (tNode*)pGraph->Nodes.pElements + idxFrom; 
    pTo = (tNode*)pGraph->Nodes.pElements + idxTo; 

    // link IdFrom -> IdTo 
    if (bsearch(&IdTo, 
       pFrom->LinksTo.pElements, 
       pFrom->LinksTo.Count, 
       pFrom->LinksTo.ElementSize, 
       &IntComparator) == NULL) // IdFrom doesn't link to IdTo yet 
    { 
    if (!ArrayInsertElement(&pFrom->LinksTo, pFrom->LinksTo.Count, &IdTo)) 
     return 0; 

    qsort(pFrom->LinksTo.pElements, 
      pFrom->LinksTo.Count, 
      pFrom->LinksTo.ElementSize, 
      &IntComparator); // maintain order for binary search 
    } 

    // back link IdFrom <- IdTo 
    if (bsearch(&IdFrom, 
       pTo->LinksFrom.pElements, 
       pTo->LinksFrom.Count, 
       pTo->LinksFrom.ElementSize, 
       &IntComparator) == NULL) // IdFrom doesn't link to IdTo yet 
    { 
    if (!ArrayInsertElement(&pTo->LinksFrom, pTo->LinksFrom.Count, &IdFrom)) 
     return 0; 

    qsort(pTo->LinksFrom.pElements, 
      pTo->LinksFrom.Count, 
      pTo->LinksFrom.ElementSize, 
      &IntComparator); // maintain order for binary search 
    } 

    return 1; 
} 

int main(void) 
{ 
    tGraph g; 

    printf("\nCreating empty graph...\n"); 
    GraphInit(&g); 
    GraphPrintNodes(&g); 

    printf("\nInserting nodes...\n"); 
    GraphInsertNode(&g, 0, 0); 
    GraphInsertNode(&g, 1, 101); 
    GraphInsertNode(&g, 2, 202); 
    GraphPrintNodes(&g); 

    printf("\nLinking nodes...\n"); 
    GraphLinkNodes(&g, 0, 1); 
    GraphLinkNodes(&g, 0, 2); 
    GraphLinkNodes(&g, 1, 2); 
    GraphLinkNodes(&g, 2, 1); 
    GraphPrintNodes(&g); 

    printf("\nDestroying graph...\n"); 
    GraphDestroy(&g); 
    GraphPrintNodes(&g); 

    // repeat 
    printf("\nLet's repeat...\n"); 

    printf("\nCreating empty graph...\n"); 
    GraphInit(&g); 
    GraphPrintNodes(&g); 

    printf("\nInserting nodes...\n"); 
    GraphInsertNode(&g, 1, 111); 
    GraphInsertNode(&g, 2, 222); 
    GraphInsertNode(&g, 3, 333); 
    GraphPrintNodes(&g); 

    printf("\nLinking nodes...\n"); 
    GraphLinkNodes(&g, 1, 2); 
    GraphLinkNodes(&g, 2, 3); 
    GraphLinkNodes(&g, 3, 1); 
    GraphPrintNodes(&g); 

    printf("\nDestroying graph...\n"); 
    GraphDestroy(&g); 
    GraphPrintNodes(&g); 

    return 0; 
} 

输出（ideone）：

Creating empty graph... 
Empty graph. 

Inserting nodes... 
Node 0: 
    Data: 0 
Node 1: 
    Data: 101 
Node 2: 
    Data: 202 

Linking nodes... 
Node 0: 
    Data: 0 
    Links to: 
    Node 1 
    Node 2 
Node 1: 
    Data: 101 
    Links to: 
    Node 2 
Node 2: 
    Data: 202 
    Links to: 
    Node 1 

Destroying graph... 
Empty graph. 

Let's repeat... 

Creating empty graph... 
Empty graph. 

Inserting nodes... 
Node 1: 
    Data: 111 
Node 2: 
    Data: 222 
Node 3: 
    Data: 333 

Linking nodes... 
Node 1: 
    Data: 111 
    Links to: 
    Node 2 
Node 2: 
    Data: 222 
    Links to: 
    Node 3 
Node 3: 
    Data: 333 
    Links to: 
    Node 1 

Destroying graph... 
Empty graph.