队列的JS实现及广度优先搜索（BFS）的实现

joywek 发布于2019-08-23 12:43 / 3035人阅读

摘要：增加删除获取队首元素是否为空以上就实现了队列的数据结构，那么队列这种数据结构有什么作用呢在广度优先搜索中，很适合队列。队列可以用在中，下面我们来实现一个广度优先搜索的例子，返回目标节点深度。

队列是先进先出（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搜索界面的实现

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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