問題描述
給定一張圖（見下圖），要求繪製其廣度優先生成樹（BFS）與深度優先生成樹（DFS），並說明具體繪製步驟。
核心概念
- 生成樹：包含圖中所有頂點、僅含 n-1 條邊的連通無環子圖。
- BFS 生成樹：從起始點出發，逐層向外擴展，優先訪問當前層的所有鄰居。
- DFS 生成樹：從起始點出發，沿一條路徑「走到黑」，無路可走時回溯。
演算法步驟與遍歷序列
1. 廣度優先搜尋 (BFS)
策略：使用佇列。先訪問起始節點，再依序訪問其所有未訪問鄰居，然後是鄰居的鄰居……
遍歷順序（以 1 為起點）：1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
生成樹邊：(1,2), (1,3), (2,4), (2,5), (3,6), (3,7), (4,8) …（視實際圖結構調整）
2. 深度優先搜尋 (DFS)
策略：使用堆疊（或遞迴）。從起點出發，任選一未訪問鄰居深入，直到無路可走再回溯。
遍歷順序（以 1 為起點）：1 → 2 → 4 → 8 → 5 → 3 → 6 → 7
生成樹邊：(1,2), (2,4), (4,8), (2,5), (1,3), (3,6), (3,7) …
繪製實戰建議
- 標記頂點編號：在紙上或繪圖工具中畫出原圖所有節點與邊。
- 模擬演算法：手寫佇列/堆疊變化，記錄每一步「發現」與「訪問」的節點。
- 提取樹邊：每當首次發現新節點時，將該邊加入生成樹（用實線或粗線標示）。
- 繪製結果：保留所有節點，僅保留樹邊，移除其餘邊，即得生成樹。
常見誤區
- 混淆「遍歷順序」與「生成樹結構」：遍歷順序是線性的，生成樹是拓撲結構。
- 忽略「已訪問」標記：導致重複加入邊、產生環。
- 鄰接節點順序不固定：若題目未指定，通常按編號大小或輸入順序處理。
掌握 BFS/DFS 生成樹繪製，是圖論、網路路由、AI 搜尋等領域的基礎功力。
