[演算法] 深度優先搜尋(DFS)

DFS，深度優先搜尋(Depth First Search)的簡稱，又稱為縱向搜尋法。

＊什麼是DFS？
顧名思義，是以Depth，也就是深度為優先考量的一種搜尋法。所謂的搜尋法，在圖論
中，就是把所有的節點(node)走一遍的方法。

也就是我以走得深為優先考量，當遇到末端時，才走向其他的路。
請注意所謂走得深是指「比這層深」，而不是在於「哪條比較深」，所以只要是比自
己深的點就可以走。而且，在一個點上的時候，我們只會知道有跟它連接的路有哪些，
而不知道這些點通往哪裡。

另外，DFS通常也會有著「循序」、「漸增」的特質，也就是當我們要從1開始走，可
以走的點有3 4 5三個， 那麼我們會先走到3，然後等到三那條走到底了，才會回來
走4，同理走完4才會走5這樣。(不過其實這是一種習慣，並非絕對，如果你要漸減也
是可以的。)

DFS的用途非常廣泛，不一定要侷限用於「圖的搜尋」，一般像是排列組合、尤拉路徑
、八皇后問題等等的，都可以用到DFS。

＊從圖型來看
現在我們有一個圖型如下：
5
／ ＼
1－2－4－8
＼ ／｜
3－6－7

假設起點是1，連接的點有2和3，那麼以深度優先往下看會先走到2
5
／ ＼
1－2－4－8
＼ ／｜
3－6－7
以2有連接的點來說：
1.走走過的點一定是繞路
2.以深度優先為考量
3.循序漸增的特質
所以在4.5之中我們會先走到4
5
／ ＼
1－2－4－8
＼ ／ ｜
3－6－7
4就沒有什麼好疑惑的了，往下繼續便可以走到8
5
／ ＼
1－2－4－8
＼ ／｜
3－6－7
以8來說呢，他會在5 6 7之中先走到5
可是走到5就可以發現：沒有其他未走過而且可以走的路可以走
這時我們便有一個back倒退的動作；也就是會回到上一個「仍有其他路可走」的點
所以走過5之後，便又會走回8

//順帶一提，back回去的這個動作，一般來說我們稱為backtracing，也就是回溯
//其意義就是搜尋所有可能解，並於失敗時回到上一步再找其它可能解

而這時8，就可以選擇往6走去
5
／ ＼
1－2－4－8
＼ ／｜
3－6－7
這時6就可以走到3或7

同樣地先走3，然後發現3沒法走其他路
就會退回6
然後走到7 這時所有的點就都被走完了
我們來看一下只保留走過路徑的圖形：
5
＼
1－2－4－8
／
3－6－7
而其拜訪順序則為1 2 4 8 5 6 3 7

/****************************************************************/
/* 練習時間
/* 5－7
/* (1) ／| ＼ 其深度優先搜尋的拜訪順序為何？
/* 1－3－4－6
/* ＼ |
/* 8－9
/* (2) 1-2-3-4-8
/* \ /
/* 7-5-6
/****************************************************************/

＊實做的方式
一般而言，我們會使用遞迴或是堆疊、串列的方式來實做
普遍來說以使用遞迴較為簡單、乾淨，也能讓程式呈現簡潔有力的感覺。
至於路徑，也就是有沒有路，我們也可以使用二維陣列來表現
1 2 3 4 5 5
1 0 1 0 1 1 / \
2 1 0 0 1 0 1-2 3 像左邊那樣的一個二維陣列，
3 0 0 0 1 1 \ | / 就可以表示這個圖
4 1 1 1 0 0 4
5 1 0 1 0 0
補充：
遞迴其實在電腦裡面是在幕後幫你做好了很多事情。
早期的程式語言並不支援遞迴的概念
實際上遞迴是有用到堆疊的暫存區的