資訊專欄INFORMATION COLUMN
摘要：廣度優(yōu)先搜索上一次已經(jīng)提到，圖的遍歷一般有兩種算法，即廣度優(yōu)先和深度優(yōu)先。其中廣度優(yōu)先搜索算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的相鄰點，就像一次訪問圖的一層。其它最短路徑算法對于加權(quán)圖的最短路徑，廣度優(yōu)先算法可能并不合適。
廣度優(yōu)先搜索（BFS）
上一次已經(jīng)提到，圖的遍歷一般有兩種算法，即廣度優(yōu)先和深度優(yōu)先。其中廣度優(yōu)先搜索算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的相鄰點，就像一次訪問圖的一層。換句話說，就是先寬后深地訪問頂點，如圖1。
圖1
從頂點v開始的廣度優(yōu)先搜索的步驟如下：
創(chuàng)建一個隊列Q。
將v標注為被發(fā)現(xiàn)的（灰色） ，并將v入隊列Q。
如果Q非空，則運行以下步驟：
將u從隊列Q中取出
將u標注為被發(fā)現(xiàn)的（灰色）
將u所有未被訪問過的鄰節(jié)點（白色）加入隊列
將u標注為已被探索的（黑色）
我們用三種狀態(tài)來反映頂點的狀態(tài)：
白色：表示該頂點還沒有被訪問。
灰色：表示該頂點被訪問過，但并未被探索過。
黑色：表示該頂點被訪問過且被完全探索過。
因此在算法開始執(zhí)行時，需要將所有頂點置為白色；如下代碼所示（本文的所有代碼都是在圖中實現(xiàn)的Graph類中添加的），其中vertices保存著圖所有頂點的名字。
function Graph() {
var vertices = [];
var adjList = new Dictionary();
// 圖類的其他代碼省略...
var initializeColor = function(){
var color = [];
for (var i=0; i
廣度優(yōu)先搜索算法的核心代碼如下，其中隊列Queue的實現(xiàn)參考基于JavaScript的數(shù)據(jù)結(jié)構(gòu) — 隊列的實現(xiàn)
this.bfs = function(v, callback){
var color = initializeColor(), // 將所有頂點初始化為白色
queue = new Queue(); // 實例化隊列
queue.enqueue(v); // 將起始頂點v加入隊列
while (!queue.isEmpty()){ // 一直循環(huán)處理隊列，直到隊列為空
var u = queue.dequeue(), // 移除隊列頂部的元素，并取得該頂點
neighbors = adjList.get(u); // 獲取該頂點的相鄰頂點
color[u] = "grey"; // 將該頂點置為灰色，表明該頂點被訪問過，但并未被探索過
for (var i=0; i
使用BFS尋找最短路徑
由于廣度優(yōu)先算法是一層層往下遍歷的，即先訪問與起始頂點距離為1的點，再訪問距離為2的點，以此類推。因此，給定一個圖G和源頂點v， 要找出每一個頂點u與v之間的最短距離（以邊的數(shù)量計算），可以在上述代碼的基礎(chǔ)上做一定修改（修改的位置用空行隔開）：
// 獲取路徑信息
this.pathData = function(v){
var color = initializeColor(),
queue = new Queue(),
d = new Array(vertices.length).fill(0), // 用于保存起始頂點v到任意頂點u的距離
pred = new Array(vertices.length).fill(null); // 用于保存v到u的路徑上u的上一級頂點（前溯點）
queue.enqueue(v);
while (!queue.isEmpty()){
var u = queue.dequeue(),
neighbors = adjList.get(u);
color[u] = "grey";
for (i=0; i 0){
s += " - " + path.pop(); // 從路徑數(shù)組倒序輸出頂點
}
console.log(s);
}
}
通過執(zhí)行Graph.printPathData(Graph.pathData())即可輸出起始頂點到每一個頂點的最短路徑。
其它最短路徑算法
對于加權(quán)圖的最短路徑，廣度優(yōu)先算法可能并不合適。比如，Dijkstra’s算法可以解決單源最短路徑問題。Bellman–Ford算法解決了邊權(quán)值為負的單源最短路徑問題。A*搜索算法解決了求僅一對頂點間的最短路徑問題，它用經(jīng)驗法則來加速搜索過程。Floyd–Warshall算法解決了求所有頂點對間的最短路徑這一問題。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/91882.html
摘要：深度優(yōu)先搜索上一次已經(jīng)提到，圖的遍歷一般有兩種算法，即廣度優(yōu)先和深度優(yōu)先。用深度優(yōu)先搜索算法對圖中的任務(wù)圖進行拓撲排序最終各頂點的發(fā)現(xiàn)和探索完成時間會保存在中。 深度優(yōu)先搜索（DFS） 上一次已經(jīng)提到，圖的遍歷一般有兩種算法，即廣度優(yōu)先和深度優(yōu)先。其中深度優(yōu)先搜索算法會從第一個指定的頂點開始遍歷圖，沿著路徑直到這條路徑最后一個頂點，接著原路回退并探索下一條路徑。換句話說，它是先深度后廣...
摘要：散列表上面的地圖向我們展示了如何用廣度優(yōu)先搜索的思想找到北京到廣州的最短路線。在廣度優(yōu)先搜索中，我們需要用到隊列的這種思想來實現(xiàn)查找。建立了下面這個模型武漢廣州西藏上海上海武漢廣州代碼完整實現(xiàn)，利用遞歸和廣度優(yōu)先搜索的思想實現(xiàn)。 什么是廣度優(yōu)先搜索？ 如果只是是背概念，幼兒園的小朋友都能背下來念給你聽。 假設(shè)看這篇文章的都和我一樣是個前端工程師，我們要從廣度優(yōu)先搜索（BFS）中學到什么...
摘要：圖關(guān)聯(lián)矩陣在關(guān)聯(lián)矩陣表示的圖中，矩陣的行表示頂點，列表示邊。如圖，頂點數(shù)是，邊的數(shù)量是，用鄰接矩陣表示圖需要的空間是，而使用關(guān)聯(lián)矩陣表示圖需要的空間是。廣度優(yōu)先搜索算法數(shù)據(jù)結(jié)構(gòu)是隊列。深度優(yōu)先搜索算法數(shù)據(jù)結(jié)構(gòu)是棧。 定義 圖和散列表、二叉樹一樣，是一種非線性數(shù)據(jù)結(jié)構(gòu)。如圖1所示，圖由一系列頂點以及連接頂點的邊構(gòu)成。由一條邊連接在一起的頂點成為相鄰頂點，比如A和B、A和D是相鄰的，而A和...
摘要：解決最短路徑問題的算法被稱為廣度優(yōu)先搜索。廣度優(yōu)先搜索算法最早由年在如何從迷宮中尋找出路這一問題中提出。廣度優(yōu)先搜索讓你能夠找出兩樣東西之間的最短距離。使用廣度優(yōu)先搜索解決問題。 你經(jīng)常需要解決最短路徑問題(shorterst-path problem)。解決最短路徑問題的算法被稱為廣度優(yōu)先搜索。廣度優(yōu)先搜索算法最早由Edward F. Moore 1959年在如何從迷宮中尋找出路這一...
閱讀 1460·2021-09-28 09:44
閱讀 2526·2021-09-28 09:36
閱讀 1199·2021-09-08 09:35
閱讀 1996·2019-08-29 13:50
閱讀 827·2019-08-29 13:29
閱讀 1146·2019-08-29 13:15
閱讀 1738·2019-08-29 13:00
閱讀 3006·2019-08-26 16:16
