深度優先搜索與廣度優先搜索

深度優先搜索的思想是盡可能深的搜索，算法藝術與信息學競賽一書中提到:隨機搜索就像是在慌亂之中找東西,因為你并不知道東西在哪,廣度優先搜索則像是你的眼鏡掉在地上之

深度優先搜索 (DFS)

深度優先搜索屬于圖算法的一種，英文縮寫為DFS即Depth First Search.其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次；

采用的搜索方法的特點是盡可能先對縱深方向進行搜索。

基本思路編輯

深度優先遍歷圖的方法是，從圖中某頂點v出發：
（1）訪問頂點v；
（2）依次從v的未被訪問的鄰接點出發，對圖進行深度優先遍歷；直至圖中和v有路徑相通的頂點都被訪問；
（3）若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發，重新進行深度優先遍歷，直到圖中所有頂點均被訪問過為止。
? 例如對于以下一個樹:
????????? 1
??????? 2?? 3
????? 4?? 5?? 6
深度優先的策略是1->2->4->退后一步->5->退后一步->退后一步->3->6->結束
而廣度優先則是第一次:1->2->3第2次:4->5->6

從深度優先的策略上看就知道深搜一般是用遞歸來實現;深度優先搜索的框架很簡單:
void DFS ( int n )
{
???? if ( 滿足結束條件,即搜索到終點 )
???????? return ;
???? else
???????? DFS ( n + 1 );
}
深搜的框架是如此簡單,但是它可能有很多變種,一般用來搜索圖,那么傳的參數就不可能只有一個那么簡單;

廣度優先搜索（BFS）

寬度優先搜索算法（又稱廣度優先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優先搜索類似的思想。其別名又叫BFS，屬于一種盲目搜尋法，目的是系統地展開并檢查圖中的所有節點，以找尋結果。換句話說，它并不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。

《算法導論》對兩種搜索都采用了很聰明的做法，用白色WHITE來標志未發現的節點，用灰色GRAY來標志第一次被發現的節點，用黑色BLACK來標志第二次被發現的節點。

對比：

深度優先搜索用棧（stack）來實現，整個過程可以想象成一個倒立的樹形：
1、把根節點壓入棧中。
2、每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。并把這個元素記為它下一級元素的前驅。
3、找到所要找的元素時結束程序。
4、如果遍歷整個樹還沒有找到，結束程序。
廣度優先搜索使用隊列（queue）來實現，整個過程也可以看做一個倒立的樹形：
1、把根節點放到隊列的末尾。
2、每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊列的末尾。并把這個元素記為它下一級元素的前驅。
3、找到所要找的元素時結束程序。
4、如果遍歷整個樹還沒有找到，結束程序。

總結

以上是生活随笔為你收集整理的深搜与广搜的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。