DFS全名Depth First Search中文叫「深度優先搜尋」，DFS是一種圖的搜尋演算法，顧名思義就是「深度」為優先去搜尋的演算法。

「深度」優先？

至於甚麼是深度為優先呢，我們來用一個比較生活化的例子來看看。
不知道大家有沒有拖地的經驗，應該有吧？國小國中高中應該都有規定要打掃教室或廁所，假設今天我要打掃的區域長這樣，那我會怎麼拖呢？

我相信男生朋友都一定跟我一樣，用肚子頂著拖把，往前衝了拉！然後在往回衝另一個方向，衝完4次我就拖完了，這其實就是深度優先的概念了呦。

所以我們可以發現，我們會先從起始點走到一個方向的盡頭，然後回到起點看看有沒有其他的路徑還沒走過，那當然有時候路可能會長這樣，那我們就要確保這邊拖完後，才會回到起始點再拖另外一條路徑。

實作DFS

在實作DFS的環節上，我們會使用Stack來實作，我把我目前的節點加入到Stack，當我Pop出來的時候，我看看這個節點還有沒有相鄰的節點，有的話我再把它加入到我的Stack，以此類推一直到我們走完所有的路徑。

也因為我們實作DFS時我們是使用Stack，因此我們還有另一個選擇，就是利用遞迴，還記得嗎遞迴底層就是Call Stack也是Stack的一種。

DFS用途

甚麼時候我們會使用DFS呢？談白說我的經驗上，其實很多的問題DFS跟BFS也就是廣度優先(之後會學到)演算法都可以使用，但是深度優先更適合用來處理那種有點像走迷宮的問題，這邊大家可以想看看迷宮問題其實就跟我們剛剛拖地的問題一樣，我把一個路徑走到底後假設是死路，那我們在回到原本的地方走其他的路。

另外DFS跟BFS不只是可以搜尋已經有路徑的圖的，也可以用來當作搜尋決策數的一種方法，有時候我們不見得會要在一個相鄰陣列中做事情，有時候我們可能會從一個狀態開始，然後我們會知道說，如果我做了一個甚麼選擇，那狀態會有甚麼改變，那個選擇也可以表示成是圖的路徑之一。

Tree Traversal與DFS

再這邊想跟大家釐清一點概念，之前我們提到過的樹的尋訪有PostOrder、PreOrder跟InOrder，這三種其實都是DFS，只是差別在我先印出哪一個節點，左、中還是右。而DFS所表達的範圍更廣，因為他包含到圖，包括有向圖跟無向圖，而樹是圖的一種，所以DFS也適用在樹上呦。

總結

DFS的觀念其實不會太複雜，但是它的用途非常廣泛，現在大家可能還沒有太多的感覺，這很正常，我以前也是這樣的，希望大家先有一個大概的觀念，之後我們開始解題的時候，就會慢慢感受DFS的厲害之處了呦！