目錄
同學們肯定或多或少的聽到過別人提起過dfs，bfs，卻一直都不太瞭解是什麼，其實兩個各為搜尋演算法，常見使用 深度優先搜尋（dfs） 以及 廣度優先搜尋（bfs） ，今天我們就來講講什麼是深度優先搜尋，深度優先就是撞到了南牆才知道回頭，才會往上一層返回。
dfs: 深度優先我們可以看出他一次只往一個方向走,直到撞到了才會返回上一層去嘗試其他結果,為上左下右的去走
bfs:廣度優先就是嘗試該位置的旁邊的所有可能,再把所有可能的能走到的所有可能繼續走.撞到了就停止,如果全部可能都'碰壁'表示從該位置無法走到終點
對比兩個遍歷方式,相信大家有了初步的www.cppcns.com認識,讓我們接下來看看這道題
題目：我們手上有編號為1~3的三個撲克牌，我們要放到編號為1 ~ 3的盒子當中，並且每個盒子中只放一張牌，問我們有多少種方法。
聰明的同學可能想一想就知道是6種了，但是當我們的要用計算機表達時我們要如何處理呢？題目雖簡單,所以我們借這道題來看看dfs如何解題.
方法一： 暴力迴圈，三層迴圈巢狀，判斷每張牌只用一次,這種方法簡單粗暴.
方法二： 深度搜尋，我們選擇把按照從小到大的依次嘗試，在第一個盒子先開始放1，這時我們剩下兩張牌，對第二個盒子來說，我們從小到大放，放2，第三個盒子只有3了，第一種放法就出來了 1 2 3。
此時我們全部牌都放完了，然後我們這時候就是撞到了南牆了，我們就開始**3，**3的時候如果我們重複放3到第三個盒子就和之前重複了，所以我們再**2，這時我們就可以把3放到第二個盒子，把2放在第三個盒子，第二種放法就出來了，1 3 2。
這時我們放完了之後再**，我們**了2，3後，1的所有可能我們就已經遍歷完了，這個時候我們就**1，這時我們就可以開始把2放到第一個盒子，這時我們還有1 ，3 ，我們按之前的從小到大的原則，把1放入第二個盒子，剩一個3放在第三個盒子，這時的第三种放法 2 1 3出來了
同理我們收兩張牌就有組合2 3 1 ，同理3 1 2 ，2 31 ，這樣我們的6種出來了，即：我們站在一個盒子，我們按照我們手中的牌，從小到大依次嘗試，即我們有一個迴圈，從第一張牌開始
//處理第index個盒子 _ - - 並行遞迴，n有多大我們就呼叫多少次
dfs(vector& box,int index,vector& visited,int n)
for(int i =1;i
下面這個是測試n張牌，n個盒子的時候，我們所有的可能，可以自行貼上複製到編輯器當中測試，請自行輸入n
void dfs(int index, int n, vector& box, vector& visited)
剛開始接觸dfs有時候會思考一些奇奇怪怪的問題,這個時候大家應該都去除錯除錯,一開始的問題一定是要解決的!!!
總結歸納：
深度優先搜尋的關鍵是解決當下應該怎麼做，下一步的做法和當下的做法是一樣的。當下的做法如何做到嘗試每一種可能，我們用for迴圈遍歷，對於每一種可能的確定後，我們繼續下一步，當前的可能等到從下一步會退之後再處理
dfs常見的模型:
dfs(當前這一步的邏輯)
員工的重要性
/*// definition for employee.
class employee ;
*/class solution
};題目的分析,題目給我們的資訊就是給到一個id,要求他的直系下屬和直系下屬的直系下屬的importance(重要度),並且vector employees,給我們一個儲存員工的資料結構,我們可以先將id和他的重要度繫結起來(雜湊表um),這樣我們用dfs遍歷的時候,就可以先處理當前id,每一個id都要處理他的vector subordina程式設計客棧tes(這個是他的直系員工的id),再去遍歷當前id的直系下屬.
for(int id: um[id]->subordinates)
// 題目答案:
class solution
}int getimportance(vector employees, int id)
int sum = um[id]->importance;//提前加上當前id的重要度
//dfs是遍歷當前id的subordinates的重要度
dfs(id, um,sum);
return sum;}};
這道題之後實際上後面的題目也都是類似的，大家從這道題開始可以嘗試自己寫一寫，再看看我的**解析，這樣幫助理解！
733. 影象渲染
這題實際上用bfs,dfs都可以,這裡我們repttxlp講的是dfs,所以我們用dfs的方式解決,一開始我的想法是,遍歷每一個位置的上下左右,將合法的位置並且是舊顏色的改成新顏色.
注：方向矩陣的概念：
int arr[4][2] =,,,};//方向矩陣
void dfs(vector>& image, int curx, int cury, int newcolor,int row ,int col,int oldcolor)
else
continue; }}
但是這樣子會有一個問題,當測試用例為新顏色和舊顏色相同的時候就會變成了死遞迴,所以我們少不了用標記矩陣,將我們走過的位置標記了他就不會重複走了。
以下為本道題的全部**
int arr[4][2] =, , , };
class solution
}vector> floodfill(vector>& image, int sr, int sc, int newcolor)
};130. 被圍繞的區域
本題就是想將全部沒有與外圍一圈o聯通的o換成x，與外界連通的o不做改變
思路：拿到這樣一道題，我們要將與外界o相連的o全部遍歷到，所以會用到深度優先搜尋，那麼我們就可以從矩陣的外圍一圈（第一行，最後一行，第一列，最後一列）出發，將外圍的每一個o都深度搜尋，將搜尋到的o（即與外界相連的先換成#）
最後再將o換成#，將#換回o。當然也可以用標記矩陣來寫，都是可以的，這裡兩種方法都寫出來看看
1.不使用標記矩陣
int arr[4][2] =, , , };
class solution
}void solve(vector>& board) ,,,};
class solution }}
void solve(vector>& board) ,,,};
class solution
}int numislands(vector>& grid) {
//這道題其實也是用bfs，dfs都可以解，用dfs的話我的思路是從第一個開始遍歷，遇到一個visited沒有訪問過的1就去遍歷他的上下左右，將他周圍的1都遍歷，在將次數加一
int row =grrepttxlpid.size();
int col=grid[0].size();
int count =0;
vector> visited(row,vector(col,0));
for(int i =0;i
695. 島嶼的最大面積
這道題留給大家作為一個小練習，有了前面的基礎，相信這道題想必不是問題！！
回溯思想dfs一些難度較大的題一起講！！dfs的學習時要注意多除錯，想清楚了再下手寫，這樣往往能夠事半功倍