百度百科關(guān)于搜索算法的定義：搜索算法是利用計算機(jī)的高性能來有目的的窮舉一個問題解空間的部分或所有的可能情況，從而求出問題的解的一種方法。從定義可知，搜索算法本質(zhì)是一種窮舉算法，是列出所有的可能性。另一方面它也是一種有目的的搜索算法，所以在窮舉的過程中需要進(jìn)行剪枝來提高執(zhí)行效率避免超時TLE。
搜索算法中常用的只要有兩種算法：深度優(yōu)先遍歷(Depth-First-Search : DFS)和廣度優(yōu)先遍歷(Breadth-First-Search : BFS)。
算法基礎(chǔ)：BFS和DFS的直觀解釋用圖的形式非常形象地概況出了兩者在求解上的差異。通過該文對BFS和DFS有了模糊的認(rèn)識。
仍然以上文的例子，如下圖，灰色代表墻壁，綠色代表起點，紅色代表終點。
BFS&DFS的異同及應(yīng)用場景
BFS
廣度優(yōu)先搜索算法BFS是一種使用隊列來保存中間狀態(tài)并最終求解的算法，其搜索過程和 “湖面丟進(jìn)一塊石頭激起層層漣漪” 類似。以走迷宮為例，最開始人在起點，首先把走一步能到的位置全都放在隊列里，走一步所到達(dá)的位置全部放入完畢后，比如A，B兩點，然后計算兩步可以到達(dá)的位置，此時需要先從隊列里取出頭節(jié)點A，然后把A一走能走到的位置插入到隊列中(假如是C、D)，然后再把B點取出，把B一步能走到的位置插入到隊列中(假如是E、F)，此時隊列變?yōu)镃、D、E、F。此時隊列中保存的是從起點兩步可達(dá)的地方。以此類推。BFS就是利用隊列先進(jìn)先出的特性，把中間節(jié)點的信息保存在隊列中，直到達(dá)到最優(yōu)解。
使用場景：一般用于求解最優(yōu)解，如最小步數(shù)，最短路徑等，但是現(xiàn)在也會有些題目會給程序員挖坑，比如求解最大的解，這時候腦海中需要判斷這個最優(yōu)解是不是漣漪最先到達(dá)的位置，如果相反是最后到達(dá)的位置，使用BFS顯然就不對了，會造成計算的空間復(fù)雜度高而使得內(nèi)存爆掉。
特點：隊列保存中間狀態(tài)，狀態(tài)的維護(hù)更新較為復(fù)雜，算法的空間復(fù)雜度高
DFS
深度優(yōu)先搜索算法DFS是一種利用遞歸實現(xiàn)的搜索算法。其搜索過程和 “不撞南墻不回頭” 類似。以走迷宮為例，DFS的走法是從起點一直走，假如從a-b-c-d，此時發(fā)現(xiàn)d點無路可走，需要退回c點繼續(xù)走，假如是a-b-c-e-f，f是出口，就走出了迷宮。這個過程中就使用了遞歸技術(shù)。
使用場景：適合搜索全部的解，比如迷宮從起點走到終點的路徑個數(shù)等等，這時顯然需要遍歷所有的解空間，而使用BFS需要記錄很多的中間狀態(tài)，使用DFS則不需要，使用遞歸非常簡單的實現(xiàn)，空間復(fù)雜度低。
特點：空間復(fù)雜度低，遞歸效率差，可能爆棧
相同點
BFS和DFS在求解過程中，一般都需要剪枝，而剪枝的好壞決定了程序運行的性能，剪枝的策略有很多，需要根據(jù)題目進(jìn)行思考，一般的剪枝策略包含：無效值剪枝、最優(yōu)性剪枝等。
另外在BFS、DFS中一般需要記錄狀態(tài)的變化，如走迷宮，BFS需要記錄當(dāng)前位置是從起點走幾步到的，如X點，可能走3 、4 、5步都可以到，但是只有第3步才有意義，因為第4、5步走的肯定不如第3步走到X點更優(yōu)。在DFS走迷宮時，也需要記錄該點是否走過。
狀態(tài)的記錄及剪枝對于算法非常重要。
代碼模板
DFS代碼模板
void dfs(depth，...)
{
if(目標(biāo)解) //
{
...//記錄當(dāng)前全局狀態(tài)信息到結(jié)果中
return;
}
for(...)//從當(dāng)前狀態(tài)擴(kuò)展下一狀態(tài)
{
if(非法狀態(tài) ) continue；
if(剪枝條件) continue；
修改全局狀態(tài)變量；
dfs(depth+1, ...)；
還原全局狀態(tài)變量；
}
}
}
BFS代碼模板
void bfs()
{
queue<Node> q;
q.push(head); //將起點插入到列表中
isvisited[head]=true; // 標(biāo)記首節(jié)點已經(jīng)被訪問：
while(!q.empty())
{
int temp=q.front();
q.pop();
for(...)//從當(dāng)前狀態(tài)擴(kuò)展下一狀態(tài)
{
if(非法狀態(tài) ) continue；
if(剪枝條件) continue；//比如被訪問過
Node next = ....;
isvisited[next]=true;
q.push(next);
}
}
關(guān)于BFS、DFS不太好用語言去描述，但是上面的這些思路有一定的指導(dǎo)意義，可以先試著做幾道題目再回來看，相信你會有收獲。
題目可以參考：
基本搜索算法(DFS|BFS)
后面我也會根據(jù)時間更新些典型代碼。
WalkeR-ZG
