DFS（Deep First Search）深度優(yōu)先搜索。

BFS（Breath First Search）廣度優(yōu)先搜索。

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

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

1.DFS（深度優(yōu)先搜索）

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

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

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

下面結(jié)合具體例子來理解。

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

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

所以我們從黑色起點首先向左走，然后發(fā)現(xiàn)還可以向左走，最后我們到達圖示位置

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

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

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

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

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

然后達到目標。DFS 的重要點在于狀態(tài)回溯。代碼如下

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

2.BFS（廣度優(yōu)先搜索）

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

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

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

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

再之后是四步，五步。

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

代碼如下

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

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

3. 總結(jié)

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

1. 數(shù)據(jù)結(jié)構(gòu)上的運用

DFS 用遞歸的形式，用到了棧結(jié)構(gòu)，先進后出。

BFS 選取狀態(tài)用隊列的形式，先進先出。

2. 復雜度

DFS 的復雜度與 BFS 的復雜度大體一致，不同之處在于遍歷的方式與對于問題的解決出發(fā)點不同，DFS 適合目標明確，而 BFS 適合大范圍的尋找。

3. 思想

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