9.1 圖的走訪DFS與BFS#

概念說明#

DFS（深度優先搜尋） 沿一條路走到不能再走，才回頭換岔路；BFS（廣度優先搜尋） 先拜訪起點的所有鄰居，再拜訪鄰居的鄰居，像水波擴散。兩者都會拜訪所有可達頂點，差別在順序與適用問題。

	DFS	BFS
資料結構	堆疊（或遞迴）	佇列
空間	O(V)（最壞路徑深）	O(V)（最寬一層）
找無權最短路	✗（找到的路未必最短）	✓
應用	找環、拓撲排序、連通分量、迷宮	無權最短路、層級分析、社交一度/二度好友

兩者都要標記已拜訪，否則有環圖會無限迴圈。

操作步驟#

DFS（遞迴）：標記 v 已拜訪 → 處理 v → 對每個未拜訪的鄰居遞迴。 BFS：起點入佇列並標記 → 取出隊首 v → 處理 v → 把未拜訪鄰居入佇列並標記 → 重複至佇列空。

Python 實作#

from collections import deque

def dfs(graph, start, visited=None):
    visited = visited or set()
    visited.add(start)
    order = [start]
    for nb in graph[start]:
        if nb not in visited:
            order += dfs(graph, nb, visited)
    return order

def dfs_iter(graph, start):           # 迭代版（顯式堆疊）
    visited, order = {start}, []
    stack = [start]
    while stack:
        v = stack.pop()
        order.append(v)
        for nb in reversed(graph[v]):  # 反轉使小號碼先被拜訪
            if nb not in visited:
                visited.add(nb)
                stack.append(nb)
    return order

def bfs(graph, start):
    visited, order = {start}, []
    dist = {start: 0}                 # BFS 副產品：到起點的最短步數
    q = deque([start])
    while q:
        v = q.popleft()
        order.append(v)
        for nb in graph[v]:
            if nb not in visited:
                visited.add(nb)
                dist[nb] = dist[v] + 1
                q.append(nb)
    return order, dist

# 圖：0-1, 0-2, 1-3, 2-3, 3-4
graph = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
print("DFS:", dfs(graph, 0))               # [0, 1, 3, 2, 4]
print("BFS:", bfs(graph, 0)[0])            # [0, 1, 2, 3, 4]
print("各點最短步數:", bfs(graph, 0)[1])    # {0:0, 1:1, 2:1, 3:2, 4:3}

# 應用一：BFS 求迷宮最短路
maze = [
    "S#...",
    ".#.#.",
    ".#.#.",
    "...#E",
]
def maze_shortest(maze):
    R, C = len(maze), len(maze[0])
    start = next((r, c) for r in range(R) for c in range(C) if maze[r][c] == "S")
    q = deque([(start, 0)])
    seen = {start}
    while q:
        (r, c), d = q.popleft()
        if maze[r][c] == "E":
            return d
        for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and maze[nr][nc] != "#" and (nr, nc) not in seen:
                seen.add((nr, nc))
                q.append(((nr, nc), d + 1))
    return -1

print("迷宮最短步數:", maze_shortest(maze))   # 13

# 應用二：DFS 找環（無向圖）
def has_cycle(graph):
    visited = set()
    def dfs_check(v, parent):
        visited.add(v)
        for nb in graph[v]:
            if nb not in visited:
                if dfs_check(nb, v):
                    return True
            elif nb != parent:
                return True
        return False
    return any(v not in visited and dfs_check(v, -1) for v in graph)

print("有環？", has_cycle({0: [1], 1: [0, 2], 2: [1, 0], }))  # True

複雜度分析#

DFS 與 BFS 在相鄰串列上皆為 O(V + E)：每個頂點入隊/入棧一次、每條邊檢查兩次（無向圖）。在相鄰矩陣上為 O(V²)。空間 O(V)。

練習#

把 bfs 改成回傳「起點到每點的實際最短路徑」（不只是距離）。提示：記錄每個點的 predecessor。
實作「連通分量計數」：統計無向圖有幾個互不相連的區塊（對每個未拜訪頂點啟動一次 DFS/BFS）。
用 DFS 實作拓撲排序：對有向無環圖輸出一種合法的課程修習順序，並說明為什麼「後序的反向」就是拓撲序。