從圖表開始

Question

我知道這可能聽起來很幼稚，但有人可以請我解釋一下，我該如何在C語言中實現圖形。我已經讀過這個理論，但是我無法通過圖形編程取消這些模塊。

---

我會很感激，如果有人可以解釋如何將使用鄰接表和鄰接矩陣創建一個圖形，你會如何執行廣度優先搜索，並與一些解釋C代碼深度優先搜索

---

在此之前，我想告訴你，這不是一項家庭作業。我真的很想學圖，但買不起導師。

Answer 1

我假設這裏的圖是頂點和邊的集合。爲此，您需要一個指向結構的指針數組。這是圖的鄰接列表表示。這些結構至少有一個值，它是節點號和指向另一個結構的指針。在插入一個新的節點到圖形時，只需轉到相應的數組索引並在開始時推送該節點。這是O（1）時間插入。我的實施可能會幫助您瞭解它的真實工作方式。如果你在C方面有很好的技能，那麼理解代碼就不需要太長的時間。

// Graph implementation by adjacency list 

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

#define MAX_SIZE 1000 

typedef struct node{ 
    int number; 
    struct node * next; 
} Node; 


// U is starting node, V is ending node 
void addNode (Node *G[], int U, int V, int is_directed) 
{ 
    Node * newnode = (Node *)malloc(sizeof(Node)); 
    newnode->number = V; 
    newnode->next = G[U]; 
    G[U] = newnode; 

// 0 for directed, 1 for undirected 
    if (is_directed) 
    { 
     Node * newnode = (Node *)malloc(sizeof(Node)); 
     newnode->number = U; 
     newnode->next = G[V]; 
     G[V] = newnode; 
    } 
} 

void printgraph(Node *G[], int num_nodes) 
{ 
    int I; 
    for (I=0; I<=num_nodes; I++) 
    { 
     Node *dum = G[I]; 
     printf("%d : ",I); 
     while (dum != NULL) 
     { 
      printf("%d, ",dum->number); 
      dum =dum->next; 
     } 
     printf("\n"); 
    } 

} 



void dfs (Node *G[], int num_nodes, int start_node) 
{ 
    int stack[MAX_SIZE]; 
    int color[num_nodes+1]; 
    memset (color, 0, sizeof(color)); 
    int top = -1; 
    stack[top+1] = start_node; 
    top++; 
    while (top != -1) 
    { 
     int current = stack[top]; 
     printf("%d ",current); 
     top--; 
     Node *tmp = G[current]; 
     while (tmp != NULL) 
     { 
      if (color[tmp->number] == 0) 
      { 
       stack[top+1] = tmp->number; 
       top++; 
       color[tmp->number] = 1; 
      } 
      tmp = tmp->next; 
     } 
    } 

} 

void bfs (Node *G[], int num_nodes, int start_node) 
{ 
    int queue[MAX_SIZE]; 
    int color[num_nodes+1]; 
    memset (color, 0, sizeof (color)); 
    int front=-1, rear=-1; 
    queue[rear+1] = start_node; 
    rear++;printf("\n\n"); 
    while (front != rear) 
    { 
     front++; 
     int current = queue[front]; 
     printf("%d ",current); 

     Node *tmp = G[current]; 
     while (tmp != NULL) 
     { 
      if (color[tmp->number] == 0) 
      { 
       queue[rear+1] = tmp->number; 
       rear++; 
       color[tmp->number] = 1; 
      } 
      tmp = tmp->next; 
     } 
    } 

} 

int main(int argc, char **argv) 
{ 
    int num_nodes; 
    // For Demo take num_nodes = 4 
    scanf("%d",&num_nodes); 
    Node *G[num_nodes+1]; 
    int I; 
    for (I=0; I<num_nodes+1 ;I++) 
     G[I] = NULL; 

    addNode (G, 0, 2, 0); 
    addNode (G, 0, 1, 0); 
    addNode (G, 1, 3, 0); 
    addNode (G, 2, 4, 0); 
    addNode (G, 2, 1, 0); 
    printgraph(G, num_nodes); 
    printf("DFS on graph\n"); 
    dfs(G, num_nodes, 0); 
    printf("\n\nBFS on graph\n"); 
    bfs(G, num_nodes, 0); 

    return 0; 
} 

Answer 2

那麼，一個真正的幼稚和基本答案將是曲線圖可以在C使用包含它們的指針到其他這樣的數據結構的數據結構來表示。圖形實際上只是雙向鏈接列表，可以從單個節點獲得多個鏈接。如果你還沒有消化鏈表和雙鏈表，那將是一個很好的開始。假設你有一個鄰接表{a，b}，{b，c}，{d}，{b，e}。首先，你解析並列出你所有的獨特物品。 （一個普通的鏈表，數組，不管怎樣，它只是一個臨時的結構來幫助你，你可以繞過它，在飛行中完成，可能會獲得加速，但這很簡單。）通過這個列表，你生成一個每個項目的節點。對於每個節點，您再次通過鄰接列表並創建一個邊緣。這是指向另一個節點的節點內的指針。

最後你有一個所有節點的定期列表，所以你不會失去那個單獨的'd'節點本身。你也有一個你所有節點的圖表，所以你知道他們之間的關係。

搜索
跨圖搜索是一個非常基本的想法。從一個節點開始，比較，移動到其中一個鄰居並重新執行。儘管有很多陷阱。就像進入一個無限循環並知道何時停止一樣。

如果您想要比您可以在網上找到更好的解釋，您將不得不問更具體的問題。