資料結構與演算法
在無向圖中，各頂點的相鄰頂點如下：A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E。從頂點 A 進行遞迴的深度優先搜尋。相鄰頂點依此處列出的順序檢查，一找到尚未拜訪的頂點就立刻前往。拜訪頂點的順序為下列何者？
- AA, B, C, D, E, F
- BA, B, D, E, C, F
- CA, B, D, E, F, C
查看答案與解析
正確答案：C. A, B, D, E, F, C
從 A 前往 B，再前往 B 的相鄰頂點中第一個未拜訪的 D。D 的相鄰頂點只有已拜訪的 B，因此回到 B 再前往下一個 E，接著從 E 前往未拜訪的 F，再從 F 前往其相鄰頂點 C。所以順序為 A, B, D, E, F, C。A, B, C, D, E, F 是依離起點由近到遠拜訪的廣度優先搜尋的順序。A, B, D, E, C, F 沒有從 E 前往未拜訪的 F 就折返了，不是深度優先搜尋的順序。
- A. 這是依離起點由近到遠拜訪的廣度優先搜尋的順序。
- B. E 的相鄰頂點中有未拜訪的 F，因此在折返到 C 之前會先前往 F。
- C. 正確。盡量往前走，走到死路時才折返。