已知下圖(graph),並由節點 a 出發進行深度優先走訪(depth-first traversal),則下列何者是可能的節點走訪順序?[圖示:節點 a,b,c,d,e,f 的連接圖]

Aaebdcf
Badbcfe正確答案
Cabcfde
Dacdbef
答案與詳解

adbcfe(a→d→b→c→f→e)為合法 DFS 順序。表示原圖中至少存在足以支撐此走訪的邊集合(如 a-d、d-b、b-c、c-f,以及 f-e 或從 f 回溯後可達 e 的路徑),且每步都選擇當前節點的未訪鄰居深入。
