学习JavaScript数据结构与算法 — 广度优先搜索算法

eternalshallow 发布于2019-08-22 11:09 / 1658人阅读

摘要：广度优先搜索上一次已经提到，图的遍历一般有两种算法，即广度优先和深度优先。其中广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点，就像一次访问图的一层。其它最短路径算法对于加权图的最短路径，广度优先算法可能并不合适。

广度优先搜索（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算法解决了求所有顶点对间的最短路径这一问题。

私有云云服务器广度优先搜索算法代码最佳优先搜索算法广度优先搜索最佳优先算法

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

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