圖的走訪 — BFS, DFS(1)

之前有提到要怎麼建立一個圖，今天就要來講講要怎麼去走訪那些圖。

以下的程式碼，使用的是C++。

主要在走訪有兩種方法：DFS（深度優先搜尋）, BFS（廣度優先搜尋）

想必如果是一開始看到這個詞，一定會有很多疑問，學了這個要幹嘛，要怎麼運用？

筆者我還沒有實際應用的經驗，所以我都把它想程式是寫程式的搜尋技巧，先學起來以備不時之需。

DFS（深度優先搜尋）

前面說過DFS是一種走訪方式，所以一定會需要一個東西，讓我們去走訪。那這個東西是什麼呢？

答案就是「圖」。

如果對建立一個圖的概念還不是太清楚的話，可以點這裡先看過一遍後，再來看這篇，會比較清楚～～

深度優先搜尋法(Depth First Search)，先找一個node然後深入那個路徑做搜尋。如下圖

DFS時，我們用stack這個容器去實作。

整個流程就只有三個動作：

1. push 到 stack

2. pop 檢查是不是目標物

3. 如果沒有東西可以 push進去，回去看 stack最上面(top)的元素

stack最上面(top)的元素，就是我們目前的位子，用這個想法去看下面的圖片，可以理解得更快。

找到「出納」的過程，如下圖：

這邊可能會有疑問，為什麼一開始push進去後，又馬上把它pop掉？

這是因為這邊所做的 pop，代表的意義就是要去檢查是不是目標 node

是的話：搜尋成功

不是的話：把跟他相鄰的 node都 push到 stack裡面

之後看到 pop時，就是代表他在做檢查的動作。

如果最後什麼東西都沒有找到的話，stack變成空，也就是說我們這次的DFS搜尋失敗。

這邊的「圖」是有方向性的圖，所以程式碼可能會跟無方向性的圖有些不一樣。

程式碼如下：（因為字串的型態會比較複雜一點，所以這邊就用數字來表示）

無向圖（Undirected Graph）的部分：

無向圖的程式碼：（使用遞迴）

這次的投影片比較多，謝謝大家能耐心看完它。

那我們BFS，就等到下一篇再來講吧。