學習JavaScript數據結構與算法 — 廣度優先搜索算法

eternalshallow 發布于2019-08-22 11:09 / 1748人閱讀

摘要：廣度優先搜索上一次已經提到，圖的遍歷一般有兩種算法，即廣度優先和深度優先。其中廣度優先搜索算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的相鄰點，就像一次訪問圖的一層。其它最短路徑算法對于加權圖的最短路徑，廣度優先算法可能并不合適。

廣度優先搜索（BFS）

上一次已經提到，圖的遍歷一般有兩種算法，即廣度優先和深度優先。其中廣度優先搜索算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的相鄰點，就像一次訪問圖的一層。換句話說，就是先寬后深地訪問頂點，如圖1。

圖1

從頂點v開始的廣度優先搜索的步驟如下：

創建一個隊列Q。

將v標注為被發現的（灰色），并將v入隊列Q。

如果Q非空，則運行以下步驟：

將u從隊列Q中取出

將u標注為被發現的（灰色）

將u所有未被訪問過的鄰節點（白色）加入隊列

將u標注為已被探索的（黑色）

我們用三種狀態來反映頂點的狀態：

白色：表示該頂點還沒有被訪問。

灰色：表示該頂點被訪問過，但并未被探索過。

黑色：表示該頂點被訪問過且被完全探索過。

因此在算法開始執行時，需要將所有頂點置為白色；如下代碼所示（本文的所有代碼都是在圖中實現的Graph類中添加的），其中vertices保存著圖所有頂點的名字。

    function Graph() {
        var vertices = [];
        var adjList = new Dictionary();
        // 圖類的其他代碼省略...
        var initializeColor = function(){
            var color = [];
            for (var i=0; i
廣度優先搜索算法的核心代碼如下，其中隊列Queue的實現參考基于JavaScript的數據結構 — 隊列的實現
   this.bfs = function(v, callback){
        var color = initializeColor(), // 將所有頂點初始化為白色
            queue = new Queue(); // 實例化隊列
        queue.enqueue(v); // 將起始頂點v加入隊列
        while (!queue.isEmpty()){ // 一直循環處理隊列，直到隊列為空
            var u = queue.dequeue(), // 移除隊列頂部的元素，并取得該頂點
                neighbors = adjList.get(u); // 獲取該頂點的相鄰頂點
            color[u] = "grey"; // 將該頂點置為灰色，表明該頂點被訪問過，但并未被探索過
            for (var i=0; i
使用BFS尋找最短路徑
由于廣度優先算法是一層層往下遍歷的，即先訪問與起始頂點距離為1的點，再訪問距離為2的點，以此類推。因此，給定一個圖G和源頂點v， 要找出每一個頂點u與v之間的最短距離（以邊的數量計算），可以在上述代碼的基礎上做一定修改（修改的位置用空行隔開）：
    // 獲取路徑信息
    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(); // 從路徑數組倒序輸出頂點
            }
            console.log(s);
        }
    }
通過執行Graph.printPathData(Graph.pathData())即可輸出起始頂點到每一個頂點的最短路徑。
其它最短路徑算法
對于加權圖的最短路徑，廣度優先算法可能并不合適。比如，Dijkstra’s算法可以解決單源最短路徑問題。Bellman–Ford算法解決了邊權值為負的單源最短路徑問題。A*搜索算法解決了求僅一對頂點間的最短路徑問題，它用經驗法則來加速搜索過程。Floyd–Warshall算法解決了求所有頂點對間的最短路徑這一問題。

云服務器 GPU云服務器廣度優先搜索算法代碼最佳優先搜索算法廣度優先搜索最佳優先算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/91882.html

學習JavaScript數據結構與算法 — 深度優先搜索算法

摘要：深度優先搜索上一次已經提到，圖的遍歷一般有兩種算法，即廣度優先和深度優先。用深度優先搜索算法對圖中的任務圖進行拓撲排序最終各頂點的發現和探索完成時間會保存在中。深度優先搜索（DFS）上一次已經提到，圖的遍歷一般有兩種算法，即廣度優先和深度優先。其中深度優先搜索算法會從第一個指定的頂點開始遍歷圖，沿著路徑直到這條路徑最后一個頂點，接著原路回退并探索下一條路徑。換句話說，它是先深度后廣...

李增田 2019-08-22 11:09 評論0 收藏0
算法系列——JavaScript中廣度優先搜索思想實現

摘要：散列表上面的地圖向我們展示了如何用廣度優先搜索的思想找到北京到廣州的最短路線。在廣度優先搜索中，我們需要用到隊列的這種思想來實現查找。建立了下面這個模型武漢廣州西藏上海上海武漢廣州代碼完整實現，利用遞歸和廣度優先搜索的思想實現。什么是廣度優先搜索？如果只是是背概念，幼兒園的小朋友都能背下來念給你聽。假設看這篇文章的都和我一樣是個前端工程師，我們要從廣度優先搜索（BFS）中學到什么...

everfly 2019-08-21 17:36 評論0 收藏0
學習JavaScript數據結構與算法 — 圖

摘要：圖關聯矩陣在關聯矩陣表示的圖中，矩陣的行表示頂點，列表示邊。如圖，頂點數是，邊的數量是，用鄰接矩陣表示圖需要的空間是，而使用關聯矩陣表示圖需要的空間是。廣度優先搜索算法數據結構是隊列。深度優先搜索算法數據結構是棧。定義圖和散列表、二叉樹一樣，是一種非線性數據結構。如圖1所示，圖由一系列頂點以及連接頂點的邊構成。由一條邊連接在一起的頂點成為相鄰頂點，比如A和B、A和D是相鄰的，而A和...

yiliang 2019-08-22 11:09 評論0 收藏0
【算法】算法圖解筆記_廣度優先搜索

摘要：解決最短路徑問題的算法被稱為廣度優先搜索。廣度優先搜索算法最早由年在如何從迷宮中尋找出路這一問題中提出。廣度優先搜索讓你能夠找出兩樣東西之間的最短距離。使用廣度優先搜索解決問題。你經常需要解決最短路徑問題(shorterst-path problem)。解決最短路徑問題的算法被稱為廣度優先搜索。廣度優先搜索算法最早由Edward F. Moore 1959年在如何從迷宮中尋找出路這一...

sanyang 2019-07-31 10:18 評論0 收藏0