本文主要關於使用 DFS 以及 BFS 遍歷圖的過程。

DFS

圖中的點有三種狀態：

  • unvisited：尚未訪問
  • in progress：訪問其相鄰節點中
  • all done：已經訪問所有相鄰節點 (皆不是 unvisited 狀態)
    初始狀態皆為 unvisited，而每個點除了各自的狀態之外，還儲存了兩個值，分別為 startTime 和 finishTime，這個等等在 Topological Sort 會用到。

pseudocode:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
DFS(w, currentTime){
    w.startTime = currentTime
    currentTime ++
    Mark w as `in progress`.
    for (v in w.neighbors){
        if (v is `unvisited`){
            currentTime = DFS(v, currentTime)
            currentTime ++
        }
    }
    w.finishTime = currentTime
    Mark w as `all done`
    return currentTime
}

應用

Topological Sort

針對有向無環圖 (Directed Acyclic Graph, DAG) 的排序法，這個排序法可以讓圖中的所有邊朝向同一個方向，並且有以下特點：當 p 點在 q 點之前，則不存在從 q 點到 p 點的路徑。

之前 DFS 遍歷時產生每個點的 finishTime，具有以下的特性：如果有 p 點指向 q 點，則 p.finishTime > q.finishTime，要證明的話可以透過 DFS tree 來觀察，如果有 p 點指向 q 點則可以分為兩種情況：

  1. 在 DFS tree 中 q 點為 p 點的子孫節點：

    時間軸

    p.startTime

    q.startTime

    q.finishTime

    p.finishTime

  2. 在 DFS tree 中 q 點不為 p 點的子孫節點
    此時必定會先經過並完成 q 點，不然 q 點就會是 p 點的子孫節點。

    時間軸

    q.startTime

    q.finishTime

    p.startTime

    p.finishTime

有了以上的特點，我們要進行 Topological Sort 就只要將各點的 finishTime 由大排到小即可，我們可以在遍歷的過程中，每完成一個節點，就將其放入 list 的頂端，最後 list 由頂端到底端就是已排序的結果。

BFS

每次向前推進一步，L_i 代表 第 i 步可以走到的點，L_0 為出發點，每次尋找 L_i 的相鄰節點，如果還沒訪問就將其放到 L_i+1 中。

pseudocode:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Set L_i = [] for i=1,...,n
L0 = [w], where w is the start node
Mark w as `visited`
for (i = 0, ..., n-1){
    for (u in L_i){
        for (each v which is a neighbor of u){
            If (v isn’t yet visited){
                mark v as visited, and put it in L_i+1
            }
            
        }
    }
}

應用

Shortest path

尋找兩個點 u 和 v 之間的最短距離與路徑 (不考慮邊的權重)，從 u 點開始執行 BFS，則對於每個點 v 在 L_i 中，u 和 v 之間的最短距離為 i，且可以在 BFS tree 中看到最短路徑。

二分圖檢驗

二分圖指的是可以將圖分成兩群點，兩群點之間有邊，兩群點的內部則無邊。

選擇一個點開始進行 BFS，將點依序塗成兩種顏色 (ex: i 為奇數時，L_i 的點為紅色，反之為藍色)，如果有任何兩個相鄰的點為同色 (形成奇環：有奇數條邊的環)，則這個圖不是二分圖。

Strongly Connected Components (SCC)

Strongly Connected Components 翻譯為強連通元件，出現在有向圖中，SCC 中的任兩個點 u 和 v 都可以找到 u -> v 和 v -> u 的路徑，一個有向圖中，可能包含多個不重疊的 SCC。

尋找 SCC

  1. 建立 DFS forest
    在有向圖中，不一定每個點都能到達另一個點，因此一次的 DFS 不一定能遍歷到所有點，進行完一次之後要在尚未遍歷到的點中找一個點在進行一次 DFS，直到所有點都遍歷到為止，這時候形成的就不只是一顆 DFS tree 了，而是由好幾棵樹組成的 DFS forest。

    在建立時要記得紀錄每個點的 startTime 和 finishTime。

  2. 將原本有向圖中的每條邊反轉 (u -> v 變為 v -> u)。

  3. 依照 finishTime 的大小排序，由最大的點開始進行 DFS，結束之後由剩下的點中最大的再次進行 DFS，直到遍歷完所有點，這時候形成的 DFS forest 中的每一顆樹就是一個 SCC 了 (每進行一次 DFS 就會找到一個 SCC)。