隊列的JS實現及廣度優先搜索（BFS）的實現

joywek 發布于2019-08-23 12:43 / 3047人閱讀

摘要：增加刪除獲取隊首元素是否為空以上就實現了隊列的數據結構，那么隊列這種數據結構有什么作用呢在廣度優先搜索中，很適合隊列。隊列可以用在中，下面我們來實現一個廣度優先搜索的例子，返回目標節點深度。

隊列是先進先出（FIFO）的數據結構，插入操作叫做入隊，只能添加在隊列的末尾；刪除操作叫做出隊，只能移除第一個元素。在JS中，用數組可以很簡單的實現隊列。

function Queue () {
    this.queue = [];
}
// 增加
Queue.prototype.enQueue = function(x) {
    this.queue.push(x);
    return true;
}
// 刪除
Queue.prototype.deQueue = function() {
    if(this.isEmpty()) {
        return false;
    }
    this.queue.shift();
    return true;    
}
// 獲取隊首元素
Queue.prototype.front = function() {
    if(this.isEmpty()) {
        return false;
    }
    this.queue[0];  
}
// 是否為空
Queue.prototype.isEmpty = function() {
    return !this.queue.length
}

以上就實現了隊列的數據結構，那么隊列這種數據結構有什么作用呢？在廣度優先搜索（BFS）中，很適合隊列。那什么是BFS。在樹的遍歷中，有兩種遍歷方式，其中一種就是從根節點一層一層的往下遍歷，這就是廣度優先；另一種是先由根節點選一條路徑直接遍歷到葉子節點，這就是深度優先搜索（DFS）。隊列可以用在BFS中，下面我們來實現一個廣度優先搜索的例子，返回目標節點深度。

        let root = {
            key: 1,
            children: [
                {
                    key:2,
                },
                {
                    key:3,
                    children:[
                        {
                            key:4,
                        }
                    ]
                }
            ]
        } // 數據源

function bfs(root, target) {
    //利用上面創建的Queue，當然也可以直接用數組實現
    let queue = new Queue();
    let step = 0;  // 根節點到目標節點之間的深度
    queue.enQueue(root); //將根節點加入
    //遍歷隊列
    while(!queue.isEmpty()) {
        step += 1;
        let len = queue.length;
        // 分層遍歷隊列，沒有目標元素則刪除該層元素，繼續遍歷下一層
        for(let i =0; i {
                    queue.enQueue(item)
                })
            }
            queue.deQueue()  //然后將遍歷過的節點刪除，
        }
    }
}

bfs(root,4)

這樣我們就完成了BFS的實現思路，大家可已參照該思路在具體的業務中靈活運用BFS。

GPU云服務器云服務器廣度優先搜索廣度優先搜索算法代碼消息隊列的實現 php搜索界面的實現

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

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

BFS,DFS 算法原理及js實現

1. 說明本文所有的算法嚴格按照《算法導論》，本文將詳細的對BFS和DFS進行分析，并提供算法的 js 實現，同時會對創建鏈表的方式進行優化 2. 圖的表示圖的表示分為對頂點集 V 的表示和對邊集 E 的表示，這里的重點是如何表示邊，邊的表示分為鄰接矩陣和鄰接鏈表這兩種表示方法，鄰接矩陣適合表示邊稠密的圖，其消耗空間為|V|*|V|,如果是無向圖，則可以用上三角矩陣或者下三角矩陣來表示，是空間...

劉德剛 2019-08-22 11:19 評論0 收藏0
js版本的BFS&DFS

摘要：隊列棧隊列是先進先出，后進后出，常用的操作是取第一個元素尾部加入一個元素。棧是后進先出，就像一個垃圾桶，后入的垃圾先被倒出來。遍歷中間過程，每一個節點入棧的時候是灰色的，出棧的時候是黑色的。 0. 前言廣度優先搜索(BFS)和深度優先搜索(DFS)，大家可能在oj上見過，各種求路徑、最短路徑、最優方法、組合等等。于是，我們不妨動手試一下js版本怎么玩。 1.隊列、棧隊列是先進先出，...

劉福 2019-08-22 16:49 評論0 收藏0
算法系列——JavaScript中廣度優先搜索思想實現

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

everfly 2019-08-21 17:36 評論0 收藏0
【你該懂一點Javascript算法系列】之【圖類】的定義及深度優先與廣度優先搜索算法

摘要：鄰接矩陣在鄰接矩陣實現中，由行和列都表示頂點，由兩個頂點所決定的矩陣對應元素表示這里兩個頂點是否相連如果相連這個值表示的是相連邊的權重。直到返回到頂點完成探索具體還有版的深度和廣度優先的算法，具體代碼奉上直達地址圖github直達地址 https://github.com/fanshyiis/... 在計算機科學中，一個圖就是一些頂點的集合，這些頂點通過一系列邊結對（連接）。頂點用圓...

qqlcbb 2019-08-23 15:17 評論0 收藏0