原住民族考試四等考試-電子工程類科計算機概要105 年第 20 題單選題
下列何者可以是下圖的深度優先搜尋（depth-first search）順序？
A1234567
B1237654正確答案
C1234576
D1472356
B正確答案
DFS 需沿一分支深入到底再回溯,符合圖結構的順序為 1237654。
為什麼答案是 B
1→2→3→7,深入到底後回溯造訪 6、5,再回到 1 造訪 4,符合 DFS 規則。
載入中…
完整詳解
Pro · 無限重點 DFS 需沿一分支深入到底再回溯,符合圖結構的順序為 1237654。
1. DFS 從 1 出發,先深入一個分支到底再回溯。
2. 推測圖結構:1 連 2、4;2 連 3、6(或類似);3 連 7 等。
3. 嘗試 (B) 1→2→3→7→6→5→4:沿 1-2-3-7 深入,回溯到 3 走 6、5,再回到 1 走 4,符合 DFS。
4. (A) 為 BFS 順序;(C)、(D) 違反鄰接或深入規則。
逐選項分析
A✕
1234567 為廣度優先(BFS)的層序展開,不是 DFS。
B✓ 正確
1→2→3→7,深入到底後回溯造訪 6、5,再回到 1 造訪 4,符合 DFS 規則。
C✕
1234576 中 7 與 6 的順序與圖中鄰接關係不符,無法以 DFS 產生。
D✕
1472356 起點 1 後直接跳到 4 再到 7,但 4 與 7 並非從同一深入路徑相連,違反 DFS。
勿把 BFS 的層序(如 1234567)誤認為 DFS;DFS 必須先深入。 
