圖的連通分量：DFS 與 BFS 雙重遍歷輸出（鄰接矩陣壓縮存儲）

無向圖連通分量查找：深度優先與廣度優先遍歷完整實現

給定無向圖（頂點 0~N-1，邊數 E），要求按頂點索引升序輸出所有連通分量，分別用 DFS 和 BFS 遍歷，相鄰頂點亦按升序訪問。本文採用下三角鄰接矩陣壓縮存儲（一維陣列），節省空間並簡化索引計算，提供完整 C 語言代碼與核心邏輯解析。

題目需求

• 輸入：N E，隨後 E 行邊 v1 v2。
• 輸出：先 DFS 結果，再 BFS 結果，每行一個連通分量，格式 { v1 v2 ... }。
• 遍歷規則：最小索引優先啟動，相鄰頂點升序訪問。

資料結構設計

typedef struct MGraph {
    int vertice;      // 頂點數
    int *edge;        // 下三角矩陣一維陣列，長度 N*(N-1)/2
    bool *visited;    // 訪問標記
} MGraph;

typedef struct Queue {
    int *elem;        // 循環佇列
    int head, tail;
    int size;
} Queue;

下三角矩陣索引映射

無向圖邊 (v1, v2)，令 v1 < v2，則在下三角矩陣中位置為：

index = v2 * (v2 - 1) / 2 + v1;

查詢邊存在性時，同理先確保 row > col 再計算索引。

核心算法

DFS 遞歸版

void DFS(MGraph *g, int v) {
    g->visited[v] = true;
    printf("%d ", v);
    // 訪問 v 之前的頂點（col < v）
    for (int col = 0; col < v; col++) {
        int idx = v * (v - 1) / 2 + col;
        if (g->edge[idx] && !g->visited[col]) DFS(g, col);
    }
    // 訪問 v 之後的頂點（row > v）
    for (int row = v + 1; row < g->vertice; row++) {
        int idx = row * (row - 1) / 2 + v;
        if (g->edge[idx] && !g->visited[row]) DFS(g, row);
    }
}

BFS 迭代版（循環佇列）

void BFS(MGraph *g, int v) {
    Queue *q = createQueue(g->vertice);
    g->visited[v] = true;
    printf("%d ", v);
    inQueue(q, v);

    while (!isEmpty(q)) {
        v = outQueue(q);
        // 同 DFS 邏輯，但訪問時即入佇列
        for (int col = 0; col < v; col++) {
            int idx = v * (v - 1) / 2 + col;
            if (g->edge[idx] && !g->visited[col]) {
                g->visited[col] = true;
                printf("%d ", col);
                inQueue(q, col);
            }
        }
        for (int row = v + 1; row < g->vertice; row++) {
            int idx = row * (row - 1) / 2 + v;
            if (g->edge[idx] && !g->visited[row]) {
                g->visited[row] = true;
                printf("%d ", row);
                inQueue(q, row);
            }
        }
    }
}

主流程

int main() {
    int N, E;
    scanf("%d %d", &N, &E);
    MGraph *g = initGraph(N); // 分配 edge、visited

    for (int i = 0; i < E; i++) {
        int v1, v2; scanf("%d %d", &v1, &v2);
        link(g, v1, v2);      // 設置 edge[index] = 1
    }

    // DFS 遍歷所有連通分量
    for (int i = 0; i < N; i++)
        if (!g->visited[i]) { printf("{ "); DFS(g, i); printf("}\n"); }

    // 重置 visited
    memset(g->visited, 0, N * sizeof(bool));

    // BFS 遍歷
    for (int i = 0; i < N; i++)
        if (!g->visited[i]) { printf("{ "); BFS(g, i); printf("}\n"); }

    return 0;
}

樣例驗證

輸入：

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

輸出：

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

複雜度分析

• 空間：O(N²) 壓縮為 N(N-1)/2 整數，N ≤ 10 時極小。
• 時間：DFS/BFS 均為 O(N²)（掃描矩陣），N 小可接受。

常見坑點

1. 索引計算：務必保證 row > col 再套公式，否則會訪問錯誤位置。
2. 訪問順序：雙重循環（先 col < v 再 row > v）確保升序訪問。
3. 佇列大小：設為 N+1 避免滿/空判斷衝突。
4. 重置 visited：DFS 結束後必須 memset 清零，否則 BFS 會漏掉分量。

這道題是「圖的基本遍歷 + 矩陣壓縮存儲 + 多連通分量處理」的綜合考察，掌握後可舉一反三應對各類圖連通性問題。