BFS 與 DFS：圖形搜尋演算法

圖形搜尋是路徑規劃的基礎。在學習 A* 之前，我們必須先掌握兩種最基本的搜尋演算法：

BFS (廣度優先搜尋)：一層一層往外探索，保證找到最短路徑（未加權圖）
DFS (深度優先搜尋)：一條路走到黑，再回頭探索其他分支

BFS：廣度優先搜尋

BFS 的概念就像「在水面上丟一顆石頭，漣漪一層一層往外擴散」。

BFS 的運作流程

1. 從起點開始，標記為「已訪問」
2. 將起點加入佇列 (Queue)
3. 當佇列不為空時：
   a. 取出佇列前端元素
   b. 訪問該元素的所有未訪問鄰居
   c. 將鄰居標記為已訪問並加入佇列
4. 重複直到找到目標或佇列為空

實作 BFS

from collections import deque

def bfs(graph, start, goal=None):
    """
    廣度優先搜尋
    graph: dict — 鄰接表表示的圖形
    start: 起點
    goal: 目標（如果為 None，則訪問所有節點）
    """
    visited = set()
    queue = deque([start])
    visited.add(start)
    parent = {start: None}  # 記錄路徑
    
    while queue:
        node = queue.popleft()
        print(f"訪問: {node}", end=" → " if node != goal else "\n")
        
        if node == goal:
            print(f"找到目標 {goal}!")
            # 重建路徑
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return list(reversed(path))
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                queue.append(neighbor)
    
    return None  # 找不到目標

# 測試：迷宮地圖
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E', 'G'],
    'G': ['F']
}

path = bfs(graph, 'A', 'G')
print(f"BFS 最短路徑: {' → '.join(path)}")

BFS 的應用

迷宮求解：保證找到最短出口
社群網路「幾度分隔」：LinkedIn 的「一度/二度人脈」
網路廣播：P2P 網路的資料擴散
垃圾回收 (GC)：Java 與 Python 的標記清除演算法

DFS：深度優先搜尋

DFS 的概念就像「在迷宮中沿著右手邊的牆一直走」。

DFS 的運作流程

1. 從起點開始，標記為「已訪問」
2. 將起點加入堆疊 (Stack)
3. 當堆疊不為空時：
   a. 取出堆疊頂端元素
   b. 如果該元素有未訪問的鄰居，選擇一個並加入堆疊
   c. 如果沒有未訪問的鄰居，回溯（彈出）
4. 重複直到找到目標或堆疊為空

實作 DFS

def dfs(graph, start, goal=None):
    """深度優先搜尋（使用堆疊）"""
    visited = set()
    stack = [start]
    parent = {start: None}
    
    while stack:
        node = stack.pop()
        
        if node not in visited:
            visited.add(node)
            print(f"訪問: {node}", end=" → ")
            
            if node == goal:
                print(f"\n找到目標 {goal}!")
                path = []
                while node is not None:
                    path.append(node)
                    node = parent[node]
                return list(reversed(path))
            
            for neighbor in reversed(graph.get(node, [])):
                if neighbor not in visited:
                    parent[neighbor] = node
                    stack.append(neighbor)
    
    print()
    return None

path = dfs(graph, 'A', 'G')
print(f"DFS 找到的路徑: {' → '.join(path)}")

DFS 的應用

拓撲排序：編譯器決定程式碼編譯順序
連通分量檢測：圖片分割、社群偵測
迷宮生成：隨機 DFS 是經典的迷宮生成演算法
語法分析樹：編譯器的 AST 遍歷

BFS vs DFS 比較

| 特性 | BFS | DFS | |------|-----|-----| | 資料結構 | 佇列 (Queue) | 堆疊 (Stack) | | 最短路徑 | ✅ 保證（未加權圖） | ❌ 不保證 | | 記憶體使用 | O(寬度)，可能很大 | O(深度)，通常較小 | | 完整度 | ✅ 一定找到解 | ✅ 一定找到解（有限圖） | | 最佳適用 | 找到最短解 | 記憶體受限、需要遍歷全部 |

實戰：迷宮生成與求解

import random

# === 使用隨機 DFS 生成迷宮 ===
def generate_maze(width, height):
    """使用 Recursive Backtracker 生成迷宮"""
    # 初始化迷宮（全部牆壁）
    maze = [[1] * (2 * width + 1) for _ in range(2 * height + 1)]
    
    # 所有格子
    grid = [(x, y) for y in range(height) for x in range(width)]
    
    # DFS 生成
    start = (0, 0)
    visited = set()
    stack = [start]
    visited.add(start)
    
    # 將起點設為通道
    maze[1][1] = 0
    
    while stack:
        x, y = stack[-1]
        neighbors = []
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < width and 0 <= ny < height and (nx, ny) not in visited:
                neighbors.append((nx, ny, dx, dy))
        
        if neighbors:
            nx, ny, dx, dy = random.choice(neighbors)
            visited.add((nx, ny))
            # 打通牆壁
            maze[2 * y + 1 + dy][2 * x + 1 + dx] = 0
            maze[2 * ny + 1][2 * nx + 1] = 0
            stack.append((nx, ny))
        else:
            stack.pop()
    
    return maze

def print_maze(maze):
    for row in maze:
        print(''.join('██' if c else '  ' for c in row))

maze = generate_maze(10, 10)
print("=== 隨機生成迷宮（10x10）===")
print_maze(maze)

# === 使用 BFS 求解迷宮 ===
def solve_maze_bfs(maze):
    """用 BFS 求解迷宮"""
    height = len(maze)
    width = len(maze[0])
    
    start = (1, 1)
    goal = (width - 2, height - 2)
    
    queue = deque([start])
    visited = {start}
    parent = {start: None}
    
    while queue:
        x, y = queue.popleft()
        
        if (x, y) == goal:
            path = []
            while (x, y) is not None:
                path.append((x, y))
                (x, y) = parent[(x, y)]
            return list(reversed(path))
        
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if (0 <= nx < width and 0 <= ny < height 
                and maze[ny][nx] == 0 and (nx, ny) not in visited):
                visited.add((nx, ny))
                parent[(nx, ny)] = (x, y)
                queue.append((nx, ny))
    
    return None

path = solve_maze_bfs(maze)
print(f"\nBFS 找到最短路徑: {len(path)} 步" if path else "找不到出口!")

使用 Vibe Coding 實作 BFS/DFS

🔥 【BFS/DFS 詠唱範例】 「請幫我實作台灣高鐵路線查詢系統： 1. 使用所有高鐵站點建立圖形。 2. 實作 BFS 找出「最少站點數」的路線。 3. 實作 DFS 找出所有可能路線。 4. 比較 BFS 與 DFS 找到的路徑差異。 5. 用 Matplotlib 畫出搜尋過程（動畫展示）。」

本日總結

在本章中，你學到了：

✅ BFS (廣度優先搜尋)：使用佇列，保證最短路徑
✅ DFS (深度優先搜尋)：使用堆疊，遍歷所有可能
✅ BFS vs DFS 比較：何時該用哪一種
✅ 迷宮生成：使用隨機 DFS 生成迷宮
✅ 迷宮求解：使用 BFS 找到最短路徑

下一章，我們將學習 Dijkstra 演算法——BFS 的加權圖版本！