跳至主要内容

Graph Traversal

如果你對於 Graph 還不熟，推薦先了解 Graph。

Graph Traversal 指的是 「把圖裡面所有的頂點都拜訪過一遍」 的過程。

因為圖（Graph）的結構非常自由，不像 Tree 有固定的上下階層（根節點），點跟點之間可能連成一個圈（環）。為了不重複造訪同個地方行程無窮迴圈，走訪時一定要有一個記錄，寫下哪些點已經去過（Visited），哪些點還沒去過。

白話理解

BFS 像是「地毯式搜索」，從起點一圈一圈往外擴散，先看完所有鄰居，再看鄰居的鄰居。
DFS 則像走迷宮，選定一條路就衝到底，撞牆才退回來換下一條路。

兩者都是「把整張 Graph 走過一遍」，差別只在於先廣後深、還是先深後廣。

Breadth First Search (BFS)​

廣度優先如同 「地毯式搜索」。

從起點開始，先拜訪所有距離一步的鄰居，再拜訪距離兩步的鄰居，一圈一圈像水滴的漣漪一樣往外擴散。

from collections import deque

class Graph:
    def __init__(self):
        self.adjacency_list = {}

    # ... 其他 method

    def bfs(self, start):
        if start not in self.adjacency_list:
            return None
        result = []
        visited = set()
        queue = deque([start])
        while queue:
            node = queue.popleft()
            if node in visited:  # 避免重複造訪
                continue
            result.append(node)
            visited.add(node)
            for neighbor in self.adjacency_list[node]:
                queue.append(neighbor)
        return result

Depth First Search (DFS)​

選定一條路就一直往前走到底，直到遇到死巷子，才往回退一步（Backtrack），換另一條分支繼續走到底。

實作上又可分為迭代 (Iteration 使用 Stack) 或 遞迴 (Recursion) 兩種做法。

Iteration​

建立一個 stack （使用 list/array）用來記錄即將要走訪的 vertex。

class Graph:
    def __init__(self):
        self.adjacency_list = {}

    # ... 其他 method

    def dfs_iterative(self, start):
        if start not in self.adjacency_list:
            return None
        result = []
        visited = set()
        stack = [start]
        while stack:
            node = stack.pop()
            if node in visited or not self.adjacency_list.get(node):
                continue
            result.append(node)
            visited.add(node)
            for neighbor in self.adjacency_list[node]:
                stack.append(neighbor)
        return result

Recursion​

class Graph:
    def __init__(self):
        self.adjacency_list = {}

    # ... 其他 method

    def dfs_recursive(self, start):
        if start not in self.adjacency_list:
            return None
        result = []
        visited = set()

        def helper(node):
            if not node or not self.adjacency_list.get(node):
                return
            result.append(node)
            visited.add(node)
            for neighbor in self.adjacency_list[node]:
                if neighbor not in visited:
                    helper(neighbor)

        helper(start)
        return result
注意

其中要注意如果用 function 這個 keyword 建立 helper 的話，裡面是沒法取得 this.adjacencyList 的，因為此時的 this 是指 helper 本身。

所以要先設一個變數 adjacencyList，讓 helper 可以取得正確的 adjacencyList。如果用箭頭函式就不用另外建立變數。

複雜度比較​

每個點（V）和每條邊（E）最多都被檢查一次。

演算法 / 實作方式時間空間說明
BFSO(V + E)O(V)Queue + 已拜訪集合 (Visited Set)
DFS (迭代 Iteration)O(V + E)O(V)Stack + 已拜訪集合
DFS (遞迴 Recursion)O(V + E)O(V)系統呼叫 Call Stack + 已拜訪集合

BFS 和 DFS 該選哪個？​

兩者都能走訪整個 Graph，但適合的場景不同：

  • BFS：適合找「最短路徑（以邊的數量計算）」，因為它是一圈一圈往外擴散，第一次抵達某個點時，走的步數保證是最少的。
  • DFS：適合「窮舉所有路徑」、「檢查連通性」或處理需要遞迴天生就比較好寫的問題（例如配合 Backtracking）。
新手小提醒

如果題目問的是「最少要幾步」或「最短距離」，先直覺想到 BFS；如果題目問的是「有沒有辦法走到」、「有幾種走法」，通常 DFS 或 Backtracking 會更直接。

延伸應用：Topological Sort​

如果 Graph 是有方向、且不能走回頭路的 DAG（Directed Acyclic Graph），DFS 還可以進一步延伸出 Topological Sort，用來排出一個「不違反任何依賴關係」的合法順序，例如課程的先修規劃。

適用情況​

  • 找最短路徑（以邊的數量計算）：例如社交網路中「你和某個人隔幾層朋友關係」，用 BFS 保證第一次抵達就是最短步數。
  • 窮舉所有可能的路徑或組合：例如走迷宮找出所有出口、島嶼數量計算，通常用 DFS 搭配 Backtracking。
  • 檢查圖的連通性：判斷兩個節點是否連通、圖中總共有幾群互不相連的節點。
  • 排出合法的執行順序：搭配 DFS 延伸出 Topological Sort，處理課程先修、任務排程等依賴關係。

常見誤區​

  • 忘記把節點加入 Visited 就往下走：務必在「把節點放進 Visited」和「往下探訪鄰居」之間確認順序一致，否則同一個節點可能被重複放進 Queue／Stack 好幾次，浪費效能甚至導致錯誤結果。
  • BFS 誤用 Stack、DFS 誤用 Queue：BFS 靠 Queue（先進先出）維持「一層一層」的順序，DFS 靠 Stack（後進先出）維持「一路走到底」的順序，兩者的資料結構不能對調，否則走訪順序會完全跑掉。
  • 忽略「圖不連通」的情況：如果 Graph 裡有些節點和起點完全沒有相連，單純從一個起點做 BFS／DFS 是無法走訪到那些節點的，如果題目要求走訪「所有」節點，需要額外對每個還沒被拜訪過的節點都各自做一次走訪。
最後於 更新