若從 a 開始以深度優先搜尋（Depth first search，簡稱 DFS）走訪下圖，何者可為其深度優先擴張樹（DFS spanning tree）？
答案與詳解
A
正確答案
DFS 擴張樹特性為「一條路走到底再回溯」，樹中不會出現根節點直接連線多個子樹且子樹間有橫向交叉連線的 BFS 結構。無向圖的 DFS 擴張樹中，所有非樹邊均為後向邊。
為什麼答案是 A
此圖呈現深度優先走訪特性。從 a 出發，DFS 會選擇一條路徑深入（例如 a→左下→最下→右側節點→...），直到該路徑無未走訪節點才回溯。選項 (A) 呈現這種細長且單一主幹深入到底再分支的結構，符合 DFS 擴張樹特性。
載入中…
完整詳解
Pro · 無限重點 DFS 擴張樹特性為「一條路走到底再回溯」，樹中不會出現根節點直接連線多個子樹且子樹間有橫向交叉連線的 BFS 結構。無向圖的 DFS 擴張樹中，所有非樹邊均為後向邊。
秒殺技巧
DFS 會盡量深入，樹的形狀通常較「深長」；BFS 會先走完同層，樹較「寬扁」。選項 (B) 根節點直接分出多支，像 BFS 樹；選項 (A) 呈現單一主幹深入到底再回溯分支，符合 DFS 深入特性。逐選項分析
A✓ 正確
此圖呈現深度優先走訪特性。從 a 出發，DFS 會選擇一條路徑深入（例如 a→左下→最下→右側節點→...），直到該路徑無未走訪節點才回溯。選項 (A) 呈現這種細長且單一主幹深入到底再分支的結構，符合 DFS 擴張樹特性。
B✕ 陷阱
此圖根節點 a 直接連線兩個子節點（左上、左下），且各自發展子樹。這符合廣度優先搜尋（BFS）先走訪所有相鄰節點的特性，而非 DFS 會先選一條路走到底的特性。
C✕
選項 (C) 的樹狀結構不符合 DFS 走訪順序。在無向圖的 DFS 擴張樹中，走訪路徑必須符合遞迴深入的特性。若圖形顯示出過早分叉導致路徑過短，或無法由 DFS 遞迴產生的結構，即非 DFS 擴張樹。
D✕
選項 (D) 同樣不符合 DFS 深入走訪的特性。DFS 擴張樹通常具有較大的深度，若選項呈現寬扁結構或邊的連線方式違反 DFS 只能產生樹邊與後向邊的性質，則為錯誤選項。
DFS 與 BFS 擴張樹比較
| 特性 | DFS 擴張樹 | BFS 擴張樹 |
|---|---|---|
| 走訪策略 | 一條路走到底再回溯 | 先走完同層再往下一層 |
| 樹的形狀 | 較深長（路徑長） | 較寬扁（層級多） |
| 非樹邊型別（無向圖） | 後向邊（連線祖先與後代） | 交叉邊（連線不同分支或同層） |
陷阱提醒
考生易將 DFS 與 BFS 的擴張樹形狀混淆。DFS 會盡量往深處走，因此樹的路徑較長；BFS 會先擴充相鄰節點，樹的寬度較大。看到根節點直接連多個子節點應聯想到 BFS。