給定下列有向圖（Directed graph），若自節點A 出發進行優先走訪（Breadth-first search），則下列何者是可能的走訪順序？

題目

給定下列有向圖（Directed graph），若自節點A 出發進行優先走訪（Breadth-first search），則下列何者是可能的走訪順序？ A. ABCDEFG B. ABDGCEF C. AGFDECB D. ABCDEGFABCDEFG

官方答案

• 答案：B. ABDGCEF

解析

廣度優先走訪（BFS）以起點 A 為第 0 層，先走訪 A 的所有相鄰節點（第 1 層），再依序走訪第 1 層各節點尚未拜訪的鄰居（第 2 層），層層向外擴展，且同一層節點不會被更遠層的節點插隊。B 的 A→B→D→G→C→E→F 呈現 A 之後先清完第一層、再進入下一層的次序，符合 BFS 特性。C 呈反向且近似深度優先的次序；A、D 則讓較遠的節點提前出現，違反逐層擴展原則。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF
• 官方答案 PDF

答案以考選部公告之測驗式試題標準答案 PDF 為準。