搜索思想——DFS & BFS（基礎基礎篇）

BFS（Breath First Search）廣度優先搜索。

今天想說一說個人對於這兩個搜索方法的見解。在我看來，DFS與BFS是演算法道路上最基礎最容易掌握的，同時，又能提供巨大助力的方法之一。我這裡斗膽用方法二字來形容DFS以及BFS，用搜索思想來囊括二者。方法是死的，而思想是活的，我們應該通過對這兩種方法的剖析來獲得這種思想，因為無論是在現實問題還是演算法題目上，問題模型都是多變的，我們要著重於理解思想而後針對特定問題能用最佳的方法去解決。

話不多說，我們先從DFS說起。

1.DFS（深度優先搜索）

講搜索當然不能撇開圖，搜索思想在圖問題中能以最直觀的方式展現。下面是我個人對於DFS的理解與概括，如果你是初學者看不懂可以結合後面舉的例子來理解，如果對於我的總結哪裡有不對的地方歡迎私信指正我。

深度優先搜索的步驟分為 1.遞歸下去 2.回溯上來。顧名思義，深度優先，則是以深度為準則，先一條路走到底，直到達到目標。這裡稱之為遞歸下去。

否則既沒有達到目標又無路可走了，那麼則退回到上一步的狀態，走其他路。這便是回溯上來。

下面結合具體例子來理解。

如圖所示，在一個迷宮中，黑色塊代表玩家所在位置，紅色塊代表終點，問是否有一條到終點的路徑

我們用深度優先搜索的方法去解這道題，由圖可知，我們可以走上下左右四個方向，我們規定按照左下右上的方向順序走，即，如果左邊可以走，我們先走左邊。然後遞歸下去，沒達到終點，我們再回溯上來，等又回溯到這個位置時，左邊已經走過了，那麼我們就走下邊，按照這樣的順序與方向走。並且我們把走過的路標記一下代表走過，不能再走。

所以我們從黑色起點首先向左走，然後發現還可以向左走，最後我們到達圖示位置

已經連續向左走到左上角的位置了，這時發現左邊不能走了，這時我們就考慮往下走，發現也不能走，同理，上邊也不能走，右邊已經走過了也不能走，這時候無路可走了，代表這條路是死路不能幫我們解決問題，所以現在要回溯上去，回溯到上一個位置，

在這個位置我們由上可知走左邊是死路不行，上下是牆壁不能走，而右邊又是走過的路，已經被標記過了，不能走。所以只能再度回溯到上一個位置尋找別的出路。

最終我們回溯到最初的位置，同理，左邊證明是死路不必走了，上和右是牆壁，所以我們走下邊。然後遞歸下去

到了這個格子，因為按照左下右上的順序，我們走左邊，遞歸下去

一直遞歸下去到最左邊的格子，然後左邊行不通，走下邊。

然後達到目標。DFS的重要點在於狀態回溯。代碼如下

int goal_x,goal_y; //目標的坐標nint graph[][]; //地圖nint used[][]; //用來標記地圖上那些點是走過的nint px[] = {-1,0,1,0}; //通過px 和 py數組來實現左下右上的移動順序nint py[] = {0,-1,0,1};nint flag = 0; //是否能達到終點的標誌nnvoid DFS(int graph[][],int used[],int x,int y)n{n if(graph[x][y] == graph[goal_x][goal_y]) //如果與目標坐標相同，則成功n {n printf("successful");n flag = 1;n return ;n }n for(int i = 0; i != 4; ++i) //遍歷四個方向n {n if(used[x + px[i]][y + py[i]] == 0 && !flag) //如果沒有走過這個格子n {n used[x + px[i]][y + py[i]] = 1; //將該格子設為走過n DFS(graph,used,x + px[i],y + py[i]); //遞歸下去n used[x + px[i]][y + py[i]] = 0;//狀態回溯，退回來，將格子設置為未走過n }n }n}n

2.BFS（廣度優先搜索）

廣度優先搜索較之深度優先搜索之不同在於，深度優先搜索旨在不管有多少條岔路，先一條路走到底，不成功就返回上一個路口然後就選擇下一條岔路，而廣度優先搜索旨在面臨一個路口時，把所有的岔路口都記下來，然後選擇其中一個進入，然後將它的分路情況記錄下來，然後再返回來進入另外一個岔路，並重複這樣的操作，用圖形來表示則是這樣的，例子同上

從黑色起點出發，記錄所有的岔路口，並標記為走一步可以到達的。然後選擇其中一個方向走進去，我們走黑點方塊上面的那個，然後將這個路口可走的方向記錄下來並標記為2，意味走兩步可以到達的地方。

接下來，我們回到黑色方塊右手邊的1方塊上，並將它能走的方向也記錄下來，同樣標記為2，因為也是走兩步便可到達的地方

這樣走一步以及走兩步可以到達的地方都搜索完畢了，下面同理，我們可以迅速把三步的格子給標記出來

再之後是四步，五步。

我們便成功尋找到了路徑，並且把所有可行的路徑都求出來了。在廣度優先搜索中，可以看出是逐步求解的，反覆的進入與退出，將當前的所有可行解都記錄下來，然後逐個去查看。在DFS中我們說關鍵點是遞歸以及回溯，在BFS中，關鍵點則是狀態的選取和標記。

代碼如下

void BFS()n{n queue que; //用隊列來保存路口n int graph[][]; //地圖n int px[] = {-1,0,1,0}; //移動方向的數組n int py[] = {0,-1,0,1};n que.push(起點入隊); //將起點入隊n while( !que.empty() ) //只要隊列不為空n {n auto temp = que.pop(); //得到隊列中的元素n for(int i = 0; i != 4; ++i)n {n if(//可以走)n {n //標記當前格子n //將當前狀態入隊列，等待下次提取n }n }n } n}n

註：以上兩個代碼只是提供思路，並非是語法正確的可運行代碼。

3.總結

對於這兩個搜索方法，其實我們是可以輕鬆的看出來，他們有許多差異與許多相同點的。

1.數據結構上的運用

DFS用遞歸的形式，用到了棧結構，先進後出。

BFS選取狀態用隊列的形式，先進先出。

2.複雜度

DFS的複雜度與BFS的複雜度大體一致，不同之處在於遍歷的方式與對於問題的解決出發點不同，DFS適合目標明確，而BFS適合大範圍的尋找。

3.思想

思想上來說這兩種方法都是窮竭列舉所有的情況。