草庐IT

广度优先遍历与最短路径

runoob 2023-04-06 原文

广度优先遍历与最短路径

广度优先遍历从某个顶点 v 出发，首先访问这个结点，并将其标记为已访问过，然后顺序访问结点v的所有未被访问的邻接点 {vi,..,vj} ，并将其标记为已访问过，然后将 {vi,...,vj} 中的每一个节点重复节点v的访问方法，直到所有结点都被访问完为止。

我们可以分为三个步骤：

  • （1）使用一个辅助队列 q，首先将顶点 v 入队，将其标记为已访问，然后循环检测队列是否为空。
  • （2）如果队列不为空，则取出队列第一个元素，并将与该元素相关联的所有未被访问的节点入队，将这些节点标记为已访问。
  • （3）如果队列为空，则说明已经按照广度优先遍历了所有的节点。

下图所示，右边蓝色表示从 0 开始遍历节点的顺序，下面是记录距离 0 的距离，可知广度优先遍历能求出无权图的最短路径。

下面用代码展示如何用广度优先遍历方式完成遍历，并且查询到最短路径。我们在上一小节代码的基础上增加一全局变量 ord 数组，记录路径中节点的次序。ord[i] 表示 i 节点在路径中的次序。同时构造函数做出相应调整，在遍历相邻节点时 每访问一个未被访问的节点进行 ord[i] = ord[v] + 1记录距离。邻接表的广度优先遍历时间复杂度为 O(V+E)，邻接矩阵的时间复杂度为O(V^2)。

...
// 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
public ShortestPath(Graph graph, int s){
    // 算法初始化
    G = graph;
    assert s >= 0 && s < G.V();

    visited = new boolean[G.V()];
    from = new int[G.V()];
    ord = new int[G.V()];
    for( int i = 0 ; i < G.V() ; i ++ ){
        visited[i] = false;
        from[i] = -1;
        ord[i] = -1;
    }
    this.s = s;
    // 无向图最短路径算法, 从s开始广度优先遍历整张图
    LinkedList<Integer> q = new LinkedList<Integer>();
    q.push( s );
    visited[s] = true;
    ord[s] = 0;
    while( !q.isEmpty() ){
        int v = q.pop();
        for( int i : G.adj(v) )
            if( !visited[i] ){
                q.push(i);
                visited[i] = true;
                from[i] = v;
                ord[i] = ord[v] + 1;
            }
    }
}
...

查看从 s 点到 w 点的最短路径长度，若从 s 到 w 不可达，返回-1。

...
public int length(int w){
    assert w >= 0 && w < G.V();
    return ord[w];
}
...

Java 实例代码

源码包下载：Download

src/runoob/graph/ShortestPath.java 文件代码：

package runoob.graph;

import runoob.graph.read.Graph;

import java.util.LinkedList;
import java.util.Stack;
import java.util.Vector;

/**
 * 广度优先遍历与最短路径
 */
public class ShortestPath {
    // 图的引用
    private Graph G;
    // 起始点
    private int s;
    // 记录dfs的过程中节点是否被访问
    private boolean[] visited;
    // 记录路径, from[i]表示查找的路径上i的上一个节点
    private int[] from;
    // 记录路径中节点的次序。ord[i]表示i节点在路径中的次序。
    private int[] ord;
    // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
    public ShortestPath(Graph graph, int s){

        // 算法初始化
        G = graph;
        assert s >= 0 && s < G.V();

        visited = new boolean[G.V()];
        from = new int[G.V()];
        ord = new int[G.V()];
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            from[i] = -1;
            ord[i] = -1;
        }
        this.s = s;
        // 无向图最短路径算法, 从s开始广度优先遍历整张图
        LinkedList<Integer> q = new LinkedList<Integer>();
        q.push( s );
        visited[s] = true;
        ord[s] = 0;
        while( !q.isEmpty() ){
            int v = q.pop();
            for( int i : G.adj(v) )
                if( !visited[i] ){
                    q.push(i);
                    visited[i] = true;
                    from[i] = v;
                    ord[i] = ord[v] + 1;
                }
        }
    }

    // 查询从s点到w点是否有路径
    public boolean hasPath(int w){
        assert w >= 0 && w < G.V();
        return visited[w];
    }
    // 查询从s点到w点的路径, 存放在vec中
    public Vector<Integer> path(int w){
        assert hasPath(w) ;
        Stack<Integer> s = new Stack<Integer>();
        // 通过from数组逆向查找到从s到w的路径, 存放到栈中
        int p = w;
        while( p != -1 ){
            s.push(p);
            p = from[p];
        }

        // 从栈中依次取出元素, 获得顺序的从s到w的路径
        Vector<Integer> res = new Vector<Integer>();
        while( !s.empty() )
            res.add( s.pop() );

        return res;
    }

    // 打印出从s点到w点的路径
    public void showPath(int w){
        assert hasPath(w) ;
        Vector<Integer> vec = path(w);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            System.out.print(vec.elementAt(i));
            if( i == vec.size() - 1 )
                System.out.println();
            else
                System.out.print(" -> ");
        }
    }
    // 查看从s点到w点的最短路径长度
    // 若从s到w不可达，返回-1
    public int length(int w){
        assert w >= 0 && w < G.V();
        return ord[w];
    }
}
广度优先广度spanstylecolor【数据结构与算法

有关广度优先遍历与最短路径的更多相关文章

  1. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  2. ruby-on-rails - Rails - 使用/自定义 URL : '/dashboard' 指定根路径 - 2

    如何使此根路径转到:“/dashboard”而不仅仅是http://example.com？root:to=>'dashboard#index',:constraints=>lambda{|req|!req.session[:user_id].blank?} 最佳答案 您可以通过以下方式实现:root:to=>redirect('/dashboard')match'/dashboard',:to=>"dashboard#index",:constraints=>lambda{|req|!req.session[:user_id].b

  3. 【Java入门】使用Java实现文件夹的遍历 - 2

    遍历文件夹我们通常是使用递归进行操作，这种方式比较简单，也比较容易理解。本文为大家介绍另一种不使用递归的方式，由于没有使用递归，只用到了循环和集合，所以效率更高一些！一、使用递归遍历文件夹整体思路1、使用File封装初始目录，2、打印这个目录3、获取这个目录下所有的子文件和子目录的数组。4、遍历这个数组，取出每个File对象4-1、如果File是否是一个文件，打印4-2、否则就是一个目录，递归调用代码实现publicclassSearchFile{publicstaticvoidmain(String[]args){//初始目录Filedir=newFile("d:/Dev");Datebeg

  4. ruby - Chef Ruby 遍历 .erb 模板文件中的属性 - 2

    所以这可能有点令人困惑，但请耐心等待。简而言之，我想遍历具有特定键值的所有属性，然后如果值不为空，则将它们插入到模板中。这是我的代码:属性:#===DefaultfileConfigurations#default['elasticsearch']['default']['ES_USER']=''default['elasticsearch']['default']['ES_GROUP']=''default['elasticsearch']['default']['ES_HEAP_SIZE']=''default['elasticsearch']['default']['MAX_OP

  5. ruby - 如何根据长度将路径数组转换为嵌套数组或散列 - 2

    我需要根据字符串路径的长度将字符串路径数组转换为符号、哈希和数组的数组给定以下数组:array=["info","services","about/company","about/history/part1","about/history/part2"]我想生成以下输出，对不同级别进行分组，根据级别的结构混合使用符号和对象。产生以下输出:[:info,:services,about:[:company,history:[:part1,:part2]]]#altsyntax[:info,:services,{:about=>[:company,{:history=>[:part1,:pa

  6. ruby - 如何遍历 Ruby 中所有正则表达式匹配的字符串？ - 2

    我们有一个字符串:“”这个正则表达式://i如何从当前字符串中获取所有匹配项？ 最佳答案 "".scan(//)参见scan在ruby​​-docs上 关于ruby-如何遍历Ruby中所有正则表达式匹配的字符串？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/6857852/

  7. ruby-on-rails - 如何播种图像的路径？ - 2

    Organization和Image具有一对一的关系。Image有一个名为filename的列，它存储文件的路径。我在Assets管道中包含这样一个文件:app/assets/other/image.jpg。播种时如何包含此文件的路径？我已经在我的种子文件中尝试过:@organization=...@organization.image.create!(filename:File.open('app/assets/other/image.jpg'))#Ialsotried:#@organization.image.create!(filename:'app/assets/other/i

  8. Ruby 和指南针路径与 yeoman 项目 - 2

    我安装了ruby​​、yeoman，当我运行我的项目时，出现了这个错误:Warning:Running"compass:dist"(compass)taskWarning:YouneedtohaveRubyandCompassinstalledthistasktowork.Moreinfo:https://github.com/gruUse--forcetocontinue.Use--forcetocontinue.我有进入可变session目标的路径，但它不起作用。谁能帮帮我？ 最佳答案 我必须运行这个:geminstallcom

  9. 对象的 Ruby 方法查找路径 - 2

    是否有内置的Ruby方法或众所周知的库可以返回对象的整个方法查找链？Ruby查看一系列令人困惑的类(如thisquestion中所讨论)以查找与消息对应的实例方法，如果没有类响应消息，则调用接收方的method_missing。我将以下代码放在一起，但我确信它遗漏了某些情况或者它是否100%正确。请指出任何缺陷并指导我找到一些更好的代码(如果存在)。defmethod_lookup_chain(obj,result=[obj.singleton_class])ifobj.instance_of?Classreturnadd_modules(result)ifresult.last==B

  10. ruby-on-rails - rails 中的路径解析 - 2

    我正在寻找这样解析路由路径的方法:ActionController::Routing.new("post_path").parse#=>{:controller=>"posts",:action=>"index"}应该和url_for相反更新我发现:Whatistheoppositeofurl_forinRails?Afunctionthattakesapathandgeneratestheinterpretedroute?ActionController::Routing::Routes.recognize_path("/posts")所以现在我需要将posts_path转换为“/p

随机推荐