C語言圖論實戰：鄰接串列表示法與深度優先搜尋（DFS）

資料結構設計

#define MAX 20
typedef struct Node {
    int num;           // 頂點編號
    struct Node *next; // 下一鄰接節點
} Node;

Node G[MAX];           // 圖的鄰接串列陣列
int visited[MAX];      // 造訪標記

建圖流程 Creategraph()

1. 初始化：每個頂點 G[i].num = i, next = NULL。
2. 對每個頂點 i，讀取鄰接頂點編號 e（輸入 0 結束）。
3. 對每個 e，malloc 新節點掛到 G[i] 串列尾部。

DFS 核心邏輯

int First(Node G[], int v) {
    return G[v].next ? G[v].next->num : -1;
}

int Next(Node G[], int v) {
    Node *p = G[v].next;
    while (p) {
        if (!visited[p->num]) return p->num;
        p = p->next;
    }
    return -1;
}

void DFS(Node G[], int v) {
    int w;
    printf("%d ", v+1);
    visited[v] = 1;
    w = First(G, v);
    while (w != -1) {
        if (!visited[w]) DFS(G, w);
        w = Next(G, v);
    }
}

主程式

int main() {
    int n;
    printf("頂點數 (≤20): ");
    scanf("%d", &n);
    Creategraph(n, G);
    for (int i=0; i<n; i++) visited[i]=0;
    printf("DFS 順序: ");
    for (int i=0; i<n; i++)
        if (!visited[i]) DFS(G, i);
    return 0;
}

關鍵點解析

• 0-based 內部，1-based 介面：內部陣列索引 0~n-1，輸入/輸出時 ±1。
• 鄰接串列動態配置：適合稀疏圖，空間 O(V+E)。
• 遞歸 DFS：程式碼簡潔，但深度過大可能堆疊溢位（圖論課程常見改寫為疊代版）。
• Next() 跳過已造訪節點：確保不重複探索同一鄰接點。

擴展建議

1. 實現廣度優先搜尋（BFS）需佇列輔助。
2. 加入邊權重，支援 Dijkstra / Prim / Kruskal。
3. 使用向量 vector<int> (C++) 或動態陣列替代手寫鏈表，簡化記憶體管理。

這個範例展示了 C 語言手動管理圖資料結構的經典模式，是理解指標操作、動態記憶體與遞歸圖算法的優秀練習。