Q235.
針對下面圖形(Graph)，以深度優先搜尋法(Depth-first Search)走訪各節點，下列之走訪順序，那些是錯的？
電腦軟體設計共同科目 · 乙級 · Q235
難易度分析
4 / 5
本題為多選題，要求考生對比多組走訪路徑的正確性。由於必須嚴格遵循圖形結構中的鄰接關係，並正確模擬遞迴回溯的過程，且需排除所有錯誤選項，因此增加了判別難度。
正確答案 (複選)：①, ③, ④
- ① ADGCFEB:ADGCFEB 為錯誤的 DFS 走訪順序。從 A→D→G 後，G 的鄰居為 D、F、C，若走 C 則 C 的鄰居為 B、E、G，此時應先走 B 或 E，但此序列在 C 之後走 F，而 F 與 C 不相鄰，違反 DFS 必須沿著相鄰邊深入的原則。
- ③ ADECBFG:ADECBFG 為錯誤的 DFS 走訪順序。從 A→D→E→C→B 後，B 的鄰居 A、C 均已走訪，應回溯至 E，但 E 的鄰居 D、F、C 中 F 尚未走訪，此序列卻在 B 之後直接跳至 F，跳過了回溯機制應經過的節點路徑。
- ④ ADECFGB:ADECFGB 為錯誤的 DFS 走訪順序。從 A→D→E→C→F 時，C 與 F 不相鄰（C 的鄰居為 B、E、G），DFS 不允許跨越非相鄰節點直接移動，違反了 DFS 必須透過鄰接矩陣或鄰接串列中存在的邊進行走訪的基本規則。
錯誤選項解析
- ② ADEFGCB:ADEFGCB 是正確的 DFS 走訪順序。從 A→D→E→F→G→C→B，每一步均沿著相鄰節點深入，符合 DFS 遞迴回溯 的特性：當 F 無未走訪鄰居時回溯至 E，再走 G，依此類推。
Learning Tip
"DFS 深度優先搜尋 的核心在於「一條路走到底，走不通再回溯」。常考陷阱包括：(1) 忽略相鄰節點限制，誤以為可跳躍至任意未走訪節點；(2) 混淆 DFS 與 BFS 的走訪順序特性；(3) 未正確模擬遞迴堆疊的回溯過程。解題時建議手動模擬堆疊變化，確認每一步是否符合鄰接關係。"
學員答題分佈
①ADGCFEB0%
②ADEFGCB0%
③ADECBFG0%
④ADECFGB0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！