圖的遍歷演算法：深度優先搜尋 (DFS) 與廣度優先搜尋 (BFS) 完整實作

遍歷核心概念

從指定頂點出發，訪問圖中所有頂點且僅訪問一次。分為兩大策略：

7.5.1 深度優先遍歷 (DFS)

類似樹的前序遍歷，遞迴實現：

1. 訪問起始頂點 V
2. 從 V 的未訪問鄰接點出發，遞迴 DFS
3. 若有未訪問頂點，選新起點重複上述過程

鄰接矩陣版 DFS

void DFS(MGraph G, int v) {
    visited[v] = TRUE;
    VisitFunc(G.vexs[v]);
    for (int w = 0; w < G.numVertexes; w++)
        if (G.arc[v][w] != INFINITY && !visited[w])
            DFS(G, w);
}

鄰接表版 DFS

void DFS(GraphAdjList GL, int v) {
    visited[v] = TRUE;
    VisitFunc(GL->adjList[v].data);
    for (EdgeNode *e = GL->adjList[v].firstedge; e; e = e->next)
        if (!visited[e->adjvex])
            DFS(GL, e->adjvex);
}

7.5.2 廣度優先遍歷 (BFS)

層層推進，需輔助佇列：

1. 訪問起始頂點 V0，入佇列
2. 佇列非空時：出佇列頂點 V，訪問其所有未訪問鄰接點並入佇列
3. 重複直到佇列為空
4. 若有未訪問頂點，選新起點重複

鄰接矩陣版 BFS

void BFS(MGraph G, int v) {
    Queue Q;
    EnQueue(Q, v);
    visited[v] = TRUE;
    VisitFunc(G.vexs[v]);
    
    while (!QueueEmpty(Q)) {
        DeQueue(Q, &v);
        for (int w = 0; w < G.numVertexes; w++) {
            if (G.arc[v][w] != INFINITY && !visited[w]) {
                visited[w] = TRUE;
                VisitFunc(G.vexs[w]);
                EnQueue(Q, w);
            }
        }
    }
}

鄰接表版 BFS

void BFS(GraphAdjList GL, int v) {
    Queue Q;
    EnQueue(Q, v);
    visited[v] = TRUE;
    VisitFunc(GL->adjList[v].data);
    
    while (!QueueEmpty(Q)) {
        DeQueue(Q, &v);
        for (EdgeNode *e = GL->adjList[v].firstedge; e; e = e->next) {
            if (!visited[e->adjvex]) {
                visited[e->adjvex] = TRUE;
                VisitFunc(GL->adjList[e->adjvex].data);
                EnQueue(Q, e->adjvex);
            }
        }
    }
}

複雜度分析

應用場景差異

• DFS：尋找路徑、拓撲排序、連通分量、解迷宮、回溯問題
• BFS：最短路徑(無權圖)、層級遍歷、最近公共祖先、社交網路六度人脈