圖的連通分量：C 語言鄰接表實現 DFS 與 BFS 遍歷

圖的連通分量：C 語言鄰接表實現 DFS 與 BFS 遍歷

本文解決 PTA《數據結構》題目「06-圖1 列出連通集」（測試點 558/4/9495）。給定無向圖，輸出所有連通分量的頂點集合，分別使用深度優先搜索（DFS）與廣度優先搜索（BFS），頂點訪問順序遞增。

圖的存儲：鄰接表

因邊數 E < n(n-1)/2，圖較稀疏，選用鄰接表：

• 頂點數組 vexs[]，每元素含 data（頂點值）與 first_edge（首邊指針）
• 邊結點 ENode：ivex（目標頂點索引）、next（下一條邊）
• 插入邊時按 ivex 升序鏈入，保證遍歷順序由小到大

#define MaxVertexNum 10
typedef int VertexType;
typedef struct ENode {
    int ivex;
    struct ENode *next;
} ENode, *PENode;
typedef struct VNode {
    VertexType data;
    ENode *first_edge;
} VNode;
typedef struct LGraph {
    int vexnum, edgnum;
    VNode *vexs;
} LGraph;

DFS 遞歸實現

void DFS(LGraph *G, int v) {
    if (!TAG) { TAG = true; printf("{ "); }
    printf("%d ", v);
    visited[v] = true;
    for (ENode *e = G->vexs[v].first_edge; e; e = e->next)
        if (!visited[e->ivex]) DFS(G, e->ivex);
}

BFS 循環隊列實現

隊列結構：

typedef struct QNode {
    int *Data; int Front, Rear, MaxSize;
} QNode, *Queue;

BFS 核心邏輯：

void BFS(LGraph *G, int v) {
    Queue Q = CreateQueue(G->vexnum);
    if (!TAG) { TAG = true; printf("{ "); }
    printf("%d ", v);
    visited[v] = true;
    AddQ(Q, v);
    while (!IsEmpty(Q)) {
        v = DeleteQ(Q);
        for (ENode *e = G->vexs[v].first_edge; e; e = e->next)
            if (!visited[e->ivex]) {
                printf("%d ", e->ivex);
                visited[e->ivex] = true;
                AddQ(Q, e->ivex);
            }
    }
    free(Q->Data); free(Q);
}

主流程：列出所有連通分量

void ListComponents(LGraph *G, void (*func)(LGraph*, int)) {
    ResetVisit();
    for (int i = 0; i < G->vexnum; i++)
        if (!visited[i]) {
            func(G, i);
            printf("}\n");
        }
}

完整可編譯代碼

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h>
#define MaxVertexNum 100  // 適當擴大

// ... 結構體定義、隊列操作、圖構建、DFS、BFS、ListComponents 如上 ...

int main() {
    LGraph *G = LGraph_new();  // 讀入頂點數、邊數、邊列表
    ListComponents(G, DFS);
    ResetVisit();
    ListComponents(G, BFS);
    LGraph_destroy(G);
    return 0;
}

輸出格式示例

輸入：

8 6
0 1
0 2
1 2
3 4
5 6
6 7

輸出：

{ 0 1 2 }
{ 3 4 }
{ 5 6 7 }
{ 8 }
{ 0 1 2 }
{ 3 4 }
{ 5 6 7 }
{ 8 }

前四行為 DFS 結果，後四行為 BFS 結果。孤立頂點 8 獨立成分量。

關鍵點總結

• 鄰接表按頂點序插入，天然滿足「遞增訪問」要求
• 全局 visited[] 陣列標記，TAG 控制大括號輸出格式
• BFS 隊列需動態分配，用完釋放避免洩漏
• 函數指針 void (*func)(LGraph*, int) 統一調用 DFS/BFS，消除重複代碼