圖的走訪— BFS, DFS(1). 之前有提到要怎麼建立一個圖 - Medium

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

主要在走訪有兩種方法：DFS（深度優先搜尋）, BFS（廣度優先搜尋）. 想必如果是一開始看到 ... GetstartedOpeninappSharonPengSigninGetstarted106FollowersAboutGetstartedOpeninapp圖的走訪—BFS,DFS(1)SharonPengSep20,2020·3minread之前有提到要怎麼建立一個圖，今天就要來講講要怎麼去走訪那些圖。

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

主要在走訪有兩種方法：DFS（深度優先搜尋）,BFS（廣度優先搜尋）想必如果是一開始看到這個詞，一定會有很多疑問，學了這個要幹嘛，要怎麼運用？筆者我還沒有實際應用的經驗，所以我都把它想程式是寫程式的搜尋技巧，先學起來以備不時之需。

DFS（深度優先搜尋）前面說過DFS是一種走訪方式，所以一定會需要一個東西，讓我們去走訪。

那這個東西是什麼呢？答案就是「圖」。

如果對建立一個圖的概念還不是太清楚的話，可以點這裡先看過一遍後，再來看這篇，會比較清楚～～深度優先搜尋法(DepthFirstSearch)，先找一個node然後深入那個路徑做搜尋。

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

整個流程就只有三個動作：1.push到stack2.pop檢查是不是目標物3.如果沒有東西可以push進去，回去看stack最上面(top)的元素stack最上面(top)的元素，就是我們目前的位子，用這個想法去看下面的圖片，可以理解得更快。

找到「出納」的過程，如下圖：這邊可能會有疑問，為什麼一開始push進去後，又馬上把它pop掉？這是因為這邊所做的pop，代表的意義就是要去檢查是不是目標node是的話：搜尋成功不是的話：把跟他相鄰的node都push到stack裡面之後看到pop時，就是代表他在做檢查的動作。

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

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

程式碼如下：（因為字串的型態會比較複雜一點，所以這邊就用數字來表示）無向圖（UndirectedGraph）的部分：無向圖的程式碼：（使用遞迴）這次的投影片比較多，謝謝大家能耐心看完它。

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

SharonPeng一起精進程式能力吧！！FollowDFSCPlusPlusLanguageMorefromSharonPengFollow一起精進程式能力吧！！