深度優先搜尋法 Depth-first search (DFS)

Depth-First Search(DFS,深度優先搜尋)的核心精神便如同Pre-Order Traversal:「先遇到的vertex就先Visiting」,並且以先遇到的vertex作為新的搜尋起點,直到所有「有edge相連的vertex」都被探索過。

以下圖迷宮為例,可以將適當寬度設唯一格,將整個迷宮設為一個矩陣, 若兩個vertex之間有路,則建立edge相連。若要在迷宮中尋找抵達終點的路線,通常會先選擇其中一條路線,只要有路就繼續往前走。有可能一路走到終點,也有可能遇到死路。若遇到死路則回到上一個岔路,往另一條路探索路線。依此類推,直到走出迷宮。

參考資料