? ? ? ? 深度優(yōu)先搜索和廣度優(yōu)先搜索凄诞，都是圖形搜索算法圆雁，它兩相似，又卻不同帆谍，在應(yīng)用上也被用到不同的地方伪朽。這里拿一起討論，方便比較汛蝙。
一烈涮、深度優(yōu)先搜索
? ? ? ? 深度優(yōu)先搜索屬于圖算法的一種，是一個針對圖和樹的遍歷算法窖剑，英文縮寫為DFS即Depth First Search坚洽。深度優(yōu)先搜索是圖論中的經(jīng)典算法，利用深度優(yōu)先搜索算法可以產(chǎn)生目標(biāo)圖的相應(yīng)拓?fù)渑判虮砦魍粒猛負(fù)渑判虮砜梢苑奖愕慕鉀Q很多相關(guān)的圖論問題讶舰，如最大路徑問題等等。一般用堆數(shù)據(jù)結(jié)構(gòu)來輔助實現(xiàn)DFS算法。其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止绘雁，而且每個節(jié)點只能訪問一次橡疼。
基本步奏
（1）對于下面的樹而言，DFS方法首先從根節(jié)點1開始庐舟，其搜索節(jié)點順序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中優(yōu)先選擇左分枝）欣除。
（2）從stack中訪問棧頂?shù)狞c；
（3）找出與此點鄰接的且尚未遍歷的點挪略，進(jìn)行標(biāo)記历帚，然后放入stack中，依次進(jìn)行杠娱；
（4）如果此點沒有尚未遍歷的鄰接點挽牢，則將此點從stack中彈出，再按照（3）依次進(jìn)行摊求；
（5）直到遍歷完整個樹禽拔，stack里的元素都將彈出，最后棧為空室叉，DFS遍歷完成睹栖。
二、廣度優(yōu)先搜索
? ? ? ? 廣度優(yōu)先搜索（也稱寬度優(yōu)先搜索茧痕，縮寫B(tài)FS野来，以下采用廣度來描述）是連通圖的一種遍歷算法這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想踪旷。其別名又叫BFS曼氛，屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點令野，以找尋結(jié)果舀患。換句話說，它并不考慮結(jié)果的可能位置彩掐，徹底地搜索整張圖构舟，直到找到結(jié)果為止《掠模基本過程狗超，BFS是從根節(jié)點開始，沿著樹(圖)的寬度遍歷樹(圖)的節(jié)點朴下。如果所有節(jié)點均被訪問努咐，則算法中止。一般用隊列數(shù)據(jù)結(jié)構(gòu)來輔助實現(xiàn)BFS算法殴胧。
基本步奏
（1）給出一連通圖渗稍，如圖佩迟，初始化全是白色（未訪問）；
（2）搜索起點V1（灰色）竿屹；
（3）已搜索V1（黑色）报强，即將搜索V2，V3拱燃，V4（標(biāo)灰）秉溉；
（4）對V2，V3碗誉，V4重復(fù)以上操作召嘶；
（5）直到終點V7被染灰，終止哮缺；
（6）最短路徑為V1弄跌，V4，V7.
