普通考試
115年
[電信工程] 計算機概要
第 19 題
若從 a 開始以深度優先搜尋（Depth first search，簡稱 DFS）走訪下圖，何者可為其深度優先擴張樹（DFS spanning tree）？
-
A
-
B
-
C
-
D
思路引導 VIP
想像你正在探索一個未知的迷宮，從入口進去後遇到一個三叉路口。如果你決定「隨便挑一條路，直到撞牆才回頭」，那麼與「在每個路口都先探頭看一眼所有分支，再往前走一步」相比，哪一種做法留下的足跡會看起來更像一條連續延伸的長線，而不是從起點散開的扇子呢？
🤖
AI 詳解
AI 專屬家教
很高興看到你準確地辨識出深度優先搜尋（DFS）的特性。在資料結構的領域中，DFS 的核心邏輯可以用「一條路走到底」來形容。當演算法從起始點 $a$ 出發時，它會優先往鄰接節點的深處探索，只有當遇到死路（所有鄰接節點都已訪問過）時，才會進行「回溯（Backtracking）」動作。因此，DFS 所產生的擴張樹，在視覺上通常呈現較長、較窄的線性結構，而非發散的扇形。
搜尋策略的結構差異
這道題目的鑑別度在於測試學生是否能直觀區分 DFS 與廣度優先搜尋（BFS）。觀察選項 (B)，你會發現它從節點 $a$ 同時向兩個分支展開，這正是 BFS 「齊頭並進」的典型特徵。而選項 (A) 則完美體現了 DFS 的走法：從 $a$ 進入下方的分支後，並未立即回頭處理 $a$ 的另一個鄰居，而是經由路徑持續向右方節點鑽研，最後才繞回上方分支。這種「寧深不廣」的特性，是判斷 DFS 擴張樹最關鍵的物理意義。
▼ 還有更多解析內容