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