初始化和圖形

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.