簡介top

深度優先搜尋 (Depth-First Search，縮稱為DFS) 是用於圖形或樹狀結構的一種搜尋演算法，每次搜尋的方向是以資料結構的深度為主，當搜尋方向觸底了還是搜尋不到目標，則退回到前一個節點，再往其他節點搜尋。

實作方式可用堆疊(Stack)結構來做搜尋可走訪的記錄。

圖形結構範例top

考慮以下圖形結構，以DFS的走訪結果會是如何?

現在我們以1這個節點作為出發點並且輸出了1，那麼現在能走的節點分別有2、3、4，因此Stack中我們就存放進了這些節點，如下圖:

由於Stack後進先出的特性，因此我們Pop了4這個節點並輸出，然後4這個節點沒有可以走的節點，因此Stack不需要Push任何節點，再來到3這個節點被Pop並輸出，而3這個節點有5和6這兩個節點可以走訪， 因此需把這兩個節點Push進Stack裡，變成如下圖:

接下來的每一步再繼續依照Stack的特性輸出，即可得到最終DFS走訪的結果，如下圖:

下一篇: 實作深度優先搜尋 (Depth-First Search)

Last updated: June 24, 2023