5.1 圖的表示法、DFS 與 BFS

學習圖時要分清兩件事：哪些關係存在，以及電腦如何儲存這些關係。 深度優先搜尋（DFS）和廣度優先搜尋（BFS）可以作用於同一幅圖，但兩者管理 前沿的規則不同，所以探索次序也不同。嚴謹的執行軌跡必須交代表示法、檢查 鄰點的次序，以及頂點在甚麼時候算作已發現。

動機

道路、通訊連線、先修關係和程式狀態都可用圖表示。圖不像陣列般有唯一的 「下一個」元素；一個頂點可以有零條、一條或多條離開它的邊。因此遍歷既要 有前沿管理待處理頂點，也要記錄哪些頂點已被發現。

• DFS 沿一條尚未完成的路徑盡量深入，適合用遞歸或堆疊（stack）表示。
• BFS 先處理最早被發現的頂點，用隊列（queue）按距離層向外擴展。

若目的只是訪問頂點，兩者都毋須使用邊權。但當每條邊成本相同時， BFS 還會計算由起點到每個可達頂點的最少邊數。

定義

依課程用語，**路徑（path）**是相鄰兩項之間都有邊的頂點序列，可以重複 頂點；**簡單路徑（simple path）**才不重複頂點。無權路徑的長度是邊數， 不是頂點數。 **迴路（cycle）**由同一頂點開始和結束；簡單迴路除首尾外不重複頂點。 沒有迴路的圖稱為無環圖。

若存在由 u 到 v 的有向路徑，便稱 v 從 u 可達。有向圖的可達性 不一定對稱。在無向圖中，兩頂點之間有路徑便是連通；每對頂點都連通的圖 稱為連通圖，而極大的連通部分稱為連通分量。有向頂點的出度數離開它的邊， 入度數進入它的邊。

選擇表示法

設頂點編號為 0,1,...,|V|-1。

表示法會直接改變取得鄰點的成本：

稠密圖或大量直接邊查詢可適合用矩陣；鄰接表不用掃描不存在的邊，因此較適合 下文的線性時間遍歷。無向邊會在兩個鄰接表各出現 一次，只多一個常數因子，不改變漸近上界。

深度優先搜尋

DFS 發現頂點後，選第一個未發現鄰點，把目前工作暫停，再深入該鄰點。遞歸 呼叫保存被暫停的工作；當某頂點沒有未發現鄰點，呼叫完成並回溯。

DFS-VISIT(u):
    discovered[u] = true
    process u
    for each v in Adj[u], in the stated order:
        if not discovered[v]:
            parent[v] = u
            DFS-VISIT(v)

DFS-FOREST(G):
    把所有頂點設為未發現，所有 parent 設為 null
    按既定次序逐一考慮頂點 u:
        if not discovered[u]:
            DFS-VISIT(u)

單次 DFS-VISIT(s) 恰好探索由 s 可達的頂點；DFS-FOREST 的外層迴圈 則會覆蓋非連通圖，每個新根開始另一棵 DFS 樹。顯式堆疊可取代遞歸，但若要 得到相同軌跡，必須小心 push 次序：一次把多個鄰點推入後進先出的堆疊，可能 令處理次序反轉。

父邊組成 DFS 樹；若使用外層迴圈，便得到 DFS 森林。它記錄每個頂點 首次如何被發現，並不代表原圖的其他邊消失。

廣度優先搜尋與前沿不變量

BFS 使用先進先出的隊列。隊列內是已發現、但出邊鄰接表尚未完全處理的頂點。 安全的發現規則是：

頂點在入隊時立即標記為已發現，不可等到日後出隊才標記。

BFS(G, s):
    for each vertex v:
        discovered[v] = false
        distance[v] = infinity
        parent[v] = null
    discovered[s] = true
    distance[s] = 0
    enqueue(Q, s)

    while Q is not empty:
        u = dequeue(Q)
        process u
        for each v in Adj[u], in the stated order:
            if not discovered[v]:
                discovered[v] = true
                distance[v] = distance[u] + 1
                parent[v] = u
                enqueue(Q, v)

discovered[v] 的賦值在 enqueue 之前。若另一個前沿頂點也有邊通往 v， 它會看到 v 已被認領，不能重複入隊。「已發現」不等於「已完成」：隊列中 的頂點雖未出隊，仍然已發現。

單次 BFS 也只處理由起點可達的部分。要遍歷無向圖的每個連通分量，便在 仍未發現的頂點重新開始 BFS，直至沒有剩餘頂點。

定理 / 命題

這結論要求每條邊成本相同。若權重不同，較少邊的路徑可以有較大總權重；普通 BFS 仍最小化邊數，卻不一定最小化加權成本。

單一起點搜尋可用實際到達的頂點和被掃描的出邊寫出更緊上界；慣常的全圖 上界對應會遍歷所有連通分量的版本。

證明思路

先證 BFS 的最短路徑性質。開始時只有 s 的距離是 0。若處理 u 時首次發現 v，算法設定 distance[v]=distance[u]+1。由於隊列是先進 先出，距離 k 的頂點一定在新發現的距離 k+1 頂點之前處理。假如 v 有 更短路徑，該路徑應從更早的層到達並更早發現 v，造成矛盾。因此首次 距離最小；每沿一個 parent 距離恰減一，parent chain 便重建最短路徑。

再證時間上界。初始化和外層迴圈是 O(|V|)。每個頂點只會首次發現一次， 所以只進遞歸/堆疊或隊列一次。所有鄰接表合計掃描每條 有向邊一次；無向邊兩次，故總時間是 O(|V|+|E|)。若用矩陣，每處理一個 頂點都要掃描 |V| 個表項，全圖遍歷便是 Theta(|V|^2)。

例題

考慮課程中的 A,B,C,D,E,F 有向圖，固定鄰接表次序如下：

A: B, D
B: C, D
C: F, D, E
D: E
E: —
F: —

    A B C D E F
A   0 1 0 1 0 0
B   0 0 1 1 0 0
C   0 0 0 1 1 1
D   0 0 0 0 1 0
E   0 0 0 0 0 0
F   0 0 0 0 0 0

常見錯誤

• 單一起點搜尋不會自動訪問不可達頂點；完整遍歷要有外層迴圈。
• 有向矩陣不必對稱，有向可達性也不必雙向成立。
• BFS 保證最少邊數，不保證任意加權成本最小。
• 一面掃描鄰接矩陣的整個 row，一面聲稱 O(|V|+|E|)，是混合了兩種表示法。
• DFS/BFS 的 parent tree 只含發現邊，不含原圖所有邊。

總結

• 圖可分為有向或無向、加權或無權。
• 路徑、迴路、可達性、連通性描述抽象圖，與儲存法分開。
• 矩陣查一條邊快但空間與 row scan 均為平方量級；鄰接表只儲存實際鄰點。
• DFS 用遞歸/堆疊先深入再回溯。
• BFS 用隊列按非遞減的邊距離層擴展。
• 穩健 BFS 在入隊時標記，保證每個頂點最多入隊一次。
• BFS 的 parent 和 distance arrays 給出無權最短路徑。
• 鄰接表 DFS/BFS 的全圖時間為 O(|V|+|E|)。

練習

1. 對 A–F 圖，寫出 C 的出邊鄰點和鄰接矩陣對應 row，並解釋鄰接表 成本為何取決於 out-degree，而矩陣 row scan 不會。
2. 先由 D 做遞歸 DFS，再由 D 做 BFS。按固定鄰接表次序寫出兩個發現 次序，並指出哪些頂點不可達。
3. 原本由 A 的 BFS 中，C 也有邊到 E，為何 E 仍由 D 得到距離 2？重建所儲存的 parent path。
4. 若 visited 標記延遲到出隊，寫出最早含重複項的隊列狀態，並 指出是哪兩條邊造成。
5. 一幅圖有 10,000 個頂點和 20,000 條有向邊。比較全圖矩陣遍歷概念上 掃描的位置數與鄰接表的漸近工作量。

解答