經典算法研究：BFS與DFS圖遍歷算法徹底講解（含遞歸/非遞歸實現）

圖的廣度優先搜索（BFS）與深度優先搜索（DFS）是圖論算法的基石，也是Dijkstra、Prim、拓撲排序、強連通分量等高級算法的核心子程序。本文對照《算法導論》，從偽代碼、顏色標記、時間戳、隊列/棧機制、遞歸與非遞歸實現五個維度，建立完整認知框架。

一、 BFS：層層擴展，求無權最短路徑

偽代碼與關鍵數據

BFS(G, s)
for each u ∈ V-{s}: color[u]=WHITE, d[u]=∞, π[u]=NIL
color[s]=GRAY, d[s]=0, π[s]=NIL
Q ← ∅; ENQUEUE(Q, s)
while Q ≠ ∅:
    u ← DEQUEUE(Q)
    for each v ∈ Adj[u]:
        if color[v] = WHITE:
            color[v] = GRAY
            d[v] = d[u] + 1
            π[v] = u
            ENQUEUE(Q, v)
    color[u] = BLACK

• WHITE：未發現；GRAY：已發現、在隊列中；BLACK：已出隊、鄰接表掃描完畢。
• d[v]：源點s到v的最短邊數（無權最短路徑）。
• π[v]：BFS樹中父節點，回溯可得最短路徑。

圖文演示

在線演示：廣度優先遍歷演示系統

複雜度

O(V+E)：每頂點入隊出隊各一次（O(V)），每邊在Adj中掃描一次（O(E)）。

二、 DFS：深度優先，時間戳記錄拓撲信息

偽代碼

DFS(G)
for each u ∈ V: color[u]=WHITE, π[u]=NIL
time ← 0
for each u ∈ V:
    if color[u] = WHITE: DFS-VISIT(u)

DFS-VISIT(u)
color[u] = GRAY
time ← time + 1; d[u] ← time      // 發現時間
for each v ∈ Adj[u]:
    if color[v] = WHITE:
        π[v] = u
        DFS-VISIT(v)
color[u] = BLACK
time ← time + 1; f[u] ← time      // 完成時間

時間戳性質（括號定理）

• d[u] < d[v] < f[v] < f[u] ⇔ v是u的後代。
• d[u] < f[u] < d[v] < f[v] ⇔ u與v無祖孫關係。
• 拓撲排序：按f[u]遞減序輸出（有向無環圖）。

圖文演示

在線演示：深度優先遍歷演示系統

複雜度

O(V+E)：每頂點DFS-VISIT恰好一次，每邊在Adj掃描一次。

三、 遞歸與非遞歸實現對比

1. 遞歸版（簡潔，受棧深度限制）

void dfsR(Graph *G, Vertex v) {
    v->marked = 1;
    visit(v);
    for (Vertex w = firstAdj(G, v); w; w = nextAdj(G, v, w))
        if (!w->marked) dfsR(G, w);
}

2. 非遞歸版（顯式棧，無棧溢出風險）

void dfsIter(Graph *G, Vertex s) {
    Stack S; push(S, s);
    while (!empty(S)) {
        Vertex v = pop(S);
        if (v->marked) continue;
        v->marked = 1;
        visit(v);
        // 注意：為模擬遞歸順序，需逆序壓棧鄰接點
        for (Vertex w = firstAdj(G, v); w; w = nextAdj(G, v, w))
            if (!w->marked) push(S, w);
    }
}

關鍵差異：遞歸隱式棧保存「下一個鄰接點索引」，非遞歸需自行管理或接受順序差異（不影響正確性）。

四、 BFS vs DFS 選型指南

五、 核心區別一句話總結

BFS 用隊列記住「下一層誰最近」，DFS 用棧（遞歸/顯式）記住「下一條路往哪鑽」。

掌握兩者的顏色機制、時間戳、父指標、隊列/棧對應關係，圖算法大廈的地基便築牢了。