兩種算法比較
廣度優(yōu)先搜索一個圖的時候是按照樹的層次來搜索的，（層次遍歷），隊列來實現(xiàn)，我們假設(shè)一個節(jié)點衍生出來的相鄰節(jié)點的平均個數(shù)是N個奋隶，那么當起點開始搜索的時候，隊列有一個節(jié)點唯欣，當起點拿出來后，把它相鄰的節(jié)點放進去搬味，那么隊列就有N個節(jié)點境氢，當下一層的搜索中再加入元素到隊列的時候，節(jié)點數(shù)達到了N2碰纬，你可以想想萍聊，一旦N是一個比較大的數(shù)的時候，這個樹的層次又比較深悦析，那這個隊列就得需要很大的內(nèi)存空間了脐区。
缺點：在樹的層次較深&&子節(jié)點個數(shù)較多的情況下，消耗內(nèi)存現(xiàn)象十分嚴重她按。因此，BFS適用于節(jié)點的子節(jié)點個數(shù)不多炕柔，并且樹的層次不會太深的情況酌泰。優(yōu)點：可以得到最優(yōu)解。與上面相對應(yīng)的匕累，DFS可以克服這個缺點陵刹，因為每次搜索的時候只需要維護一個節(jié)點，（遞歸欢嘿、棧實現(xiàn)）但回過頭想想衰琐，廣度優(yōu)先能夠找到最短路徑也糊，那深度優(yōu)先能否找到呢？深度優(yōu)先的方法是一條路走到黑羡宙，那顯然無法知道這條路是不是最短的狸剃，所以你還得繼續(xù)走別的路去判斷是否是最短路。
缺點：難以尋找最優(yōu)解狗热，僅僅只能尋找有解钞馁。其優(yōu)點就是內(nèi)存消耗小，克服了剛剛說的廣度優(yōu)先搜索的缺點匿刮。
一般說來僧凰，能用DFS解決的問題都能用BFS解決。DFS通過遞歸實現(xiàn)熟丸，易于實現(xiàn)训措，DFS的常數(shù)時間開銷會比較少，所以大多數(shù)情況下優(yōu)先考慮DFS實現(xiàn)光羞。然后就是绩鸣，DFS容易棧溢出，而BFS可以自己控制隊列的長度狞山。最后全闷，BFS加上評估函數(shù)可以變成A算法，DFS加上評估函數(shù)可以變成IDA算法萍启。
DFS算法
核心思想
它的思想是從一個頂點V0開始总珠，沿著一條路一直走到底，如果發(fā)現(xiàn)不能到達目標解勘纯，那就返回到上一個節(jié)點局服，然后從另一條路開始走到底，這種盡量往深處走的概念即是深度優(yōu)先的概念驳遵。
代碼表示如下：
/**
* DFS核心偽代碼
* 前置條件是visit數(shù)組全部設(shè)置成false
* @param n 當前開始搜索的節(jié)點
* @param d 當前到達的深度
* @return 是否有解
*/
bool DFS(Node n, int d){
if (isEnd(n, d)){//一旦搜索深度到達一個結(jié)束狀態(tài)淫奔，就返回true
return true;
}
for (Node nextNode in n){//遍歷n相鄰的節(jié)點nextNode
if (!visit[nextNode]){//
visit[nextNode] = true;//在下一步搜索中，nextNode不能再次出現(xiàn)
if (DFS(nextNode, d+1)){//如果搜索出有解
//做些其他事情堤结，例如記錄結(jié)果深度等
return true;
}
//重新設(shè)置成false唆迁，因為它有可能出現(xiàn)在下一次搜索的別的路徑中
visit[nextNode] = false;
}
}
return false;//本次搜索無解
eg.二叉樹中和為某一值的路徑
題目描述
輸入一顆二叉樹和一個整數(shù)，打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑竞穷。路徑定義為從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑唐责。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void find(TreeNode* root, int sum)
{
if (root == NULL)return;
path.push_back(root->val);
if (!root->left && !root->right && sum == root->val)
res.push_back(path);
else
{
if (root->left)
find(root->left, sum - root->val);
if (root->right)
find(root->right, sum - root->val);
}
path.pop_back();
}
vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
find(root, expectNumber);
return res;
}
};
BFS算法
核心思想
廣度優(yōu)先搜索一個圖的時候是按照樹的層次來搜索的，（層次遍歷）瘾带，隊列來實現(xiàn)鼠哥，形象的說，這里有點像輻射形狀的搜索方式，從一個節(jié)點朴恳，向其旁邊節(jié)點傳遞病毒抄罕，就這樣一層一層的傳遞輻射下去，知道目標節(jié)點被輻射中了于颖，此時就已經(jīng)找到了從起點到終點的路徑呆贿。
核心代碼如下：
/**
* 廣度優(yōu)先搜索
* @param Vs 起點
* @param Vd 終點
*/
bool BFS(Node& Vs, Node& Vd){
queue<Node> Q;
Node Vn, Vw;
int i;
//初始狀態(tài)將起點放進隊列Q
Q.push(Vs);
hash(Vw) = true;//設(shè)置節(jié)點已經(jīng)訪問過了！
while (!Q.empty()){//隊列不為空恍飘，繼續(xù)搜索榨崩！
//取出隊列的頭Vn
Vn = Q.front();
//從隊列中移除
Q.pop();
while(Vw = Vn通過某規(guī)則能夠到達的節(jié)點){
if (Vw == Vd){//找到終點了！
//把路徑記錄章母，這里沒給出解法
return true;//返回
}
if (isValid(Vw) && !visit[Vw]){
//Vw是一個合法的節(jié)點并且為白色節(jié)點
Q.push(Vw);//加入隊列Q
hash(Vw) = true;//設(shè)置節(jié)點顏色
}
}
}
return false;//無解
}
對于一個題目來說母蛛，要標志節(jié)點是否訪問過，用數(shù)組是一種很快速的方法乳怎，但有時數(shù)據(jù)量太大彩郊，很難用一個大數(shù)組來記錄時，采用hash是最好的做法蚪缀。實際上visit數(shù)組在這里也是充當hash的作用秫逝。（PS：至于hash是什么？得自己去了解询枚，它的作用是在O(1)的時間復雜度內(nèi)取出某個值）
參考資料
深度優(yōu)先算法（DFS）
廣度優(yōu)先算法（BFS）
圖的基本算法
程序員必須知道的十大算法
圖的遍歷之DFS&BFS
