寬度優先搜索
出自 MBA智库百科(https://wiki.mbalib.com/)
目錄 |
寬度優先搜索演算法，是最簡便的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型。Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。
已知圖G=(V,E)和一個源頂點s，寬度優先搜索以一種系統的方式探尋G的邊，從而“發現”s所能到達的所有頂點，並計算s到所有這些頂點的距離(最少邊數)，該演算法同時能生成一棵根為s且包括所有可達頂點的寬度優先樹。對從s可達的任意頂點v，寬度優先樹中從s到v的路徑對應於圖G中從s到v的最短路徑，即包含最小邊數的路徑。該演算法對有向圖和無向圖同樣適用。
之所以稱之為寬度優先演算法，是因為演算法自始至終一直通過已找到和未找到頂點之間的邊界向外擴展，就是說，演算法首先搜索和s距離為k的所有頂點，然後再去搜索和S距離為k+l的其他頂點。
為了保持搜索的軌跡，寬度優先搜索為每個頂點著色：白色、灰色或黑色。演算法開始前所有頂點都是白色，隨著搜索的進行，各頂點會逐漸變成灰色，然後成為黑色。在搜索中第一次碰到一頂點時，我們說該頂點被髮現，此時該頂點變為非白色頂點。因此，灰色和黑色頂點都已被髮現，但是，寬度優先搜索演算法對它們加以區分以保證搜索以寬度優先的方式執行。若(u,v)∈E且頂點u為黑色，那麼頂點v要麼是灰色，要麼是黑色，就是說，所有和黑色頂點鄰接的頂點都已被髮現。灰色頂點可以與一些白色頂點相鄰接，它們代表著已找到和未找到頂點之間的邊界。
在寬度優先搜索過程中建立了一棵寬度優先樹，起始時只包含根節點，即源頂點s.在掃描已發現頂點u的鄰接表的過程中每發現一個白色頂點v，該頂點v及邊(u,v)就被添加到樹中。在寬度優先樹中，我們稱結點u 是結點v的先輩或父母結點。因為一個結點至多只能被髮現一次，因此它最多只能有--個父母結點。相對根結點來說祖先和後裔關係的定義和通常一樣：如果u處於樹中從根s到結點v的路徑中，那麼u稱為v的祖先，v是u的後裔。
深度優先搜索用棧（stack）來實現，整個過程可以想象成一個倒立的樹形：
1、把根節點壓入棧中。
2、每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。並把這個元素記為它下一級元素的前驅。
3、找到所要找的元素時結束程式。
4、如果遍歷整個樹還沒有找到，結束程式。
廣度優先搜索使用隊列（queue）來實現，整個過程也可以看做一個倒立的樹形：
1、把根節點放到隊列的末尾。
2、每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊列的末尾。並把這個元素記為它下一級元素的前驅。
3、找到所要找的元素時結束程式。
4、如果遍歷整個樹還沒有找到，結束程式。
