广度优先遍历与最短路径(Java 实例代码源码包下载)

这篇具有很好参考价值的文章主要介绍了广度优先遍历与最短路径(Java 实例代码源码包下载)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

 文章来源地址https://www.toymoban.com/news/detail-663872.html

广度优先遍历与最短路径

Java 实例代码

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


 

广度优先遍历与最短路径

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

我们可以分为三个步骤:

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

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

 

广度优先遍历与最短路径(Java 实例代码源码包下载),数据结构与算法,JAVA,python,算法,开发语言

下面用代码展示如何用广度优先遍历方式完成遍历,并且查询到最短路径。我们在上一小节代码的基础上增加一全局变量 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];
    }
}

 

 

到了这里,关于广度优先遍历与最短路径(Java 实例代码源码包下载)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C#,图论与图算法,图(Graph)广度优先遍历(BFS,Breadth First Search)算法与源代码

    深度优先算法(DFS,Deep First Search)与 宽度优先遍历(BFS,Breadth First Search) 是树、图数据结构的基础性、标准性的遍历算法。 深度优先搜索(DFS)是一种用于搜索图形或树数据结构的算法。该算法从树的根(顶部)节点开始,尽可能沿着给定的分支(路径)向下,然后回溯

    2024年03月23日
    浏览(39)
  • 图的遍历——深度优先遍历与广度优先遍历

    目录 何谓遍历? 图的遍历特点 图的遍历方式 深度优先搜索 过程分析 案例分析: 算法的代码实现  测试案例: 测试结果如下: 遍历非连通图 算法复杂度分析 额外补充 广度优先搜索 过程分析 辅助队列 算法的代码实现 队列部分 广度搜索部分 测试案例: 测试结果: 非连

    2024年02月04日
    浏览(40)
  • 图的广度优先遍历和深度优先遍历

    前言:在上一篇博客我们学习了图的基本操作,包括图的建立、结点插入与删除等操作,怎么判断我们建立的图是否正确,很简单把它输出出来就是,但是如何输出它,这就是图的遍历问题了。 图的遍历是指从图中的某一顶点出发,按照某种搜索方法沿着图中的边对图中的所

    2024年02月11日
    浏览(50)
  • 图的两种遍历:深度优先遍历+广度优先遍历

    深度优先遍历 是指按照 深度方向 搜索,它类似于树的先根遍历,是树的先根遍历的推广。 基本思想(通俗) 选一条路走到 底 ,直到 走不通 ,就 原路返回 看看 是否还有路 可走,如果返回到起点还无路可走,说明深度优先遍历已完成。 这是要深度遍历的 无向图 :    深

    2024年02月06日
    浏览(46)
  • 蛮力算法之深度优先遍历和广度优先遍历——图的深度优先遍历和广度优先遍历,附带案例:迷宫问题及矩阵中传染性传播问题

    这两种搜索方法本质上都是基于蛮力法思路 这两种搜索方法对有向图和无向图都适用 1.1 邻接矩阵 邻接矩阵示意图: 1.2 邻接表 注意:边结点代表的是图中的边,而并非图中的结点;头结点才表示图中的结点;头结点身后所连接的为边结点 邻接表示意图:(一般默认为出边

    2024年02月05日
    浏览(65)
  • 【图】概念、存储结构、广度优先遍历遍历、深度优先遍历 - 详解

    目录 前言 一、图 1.1、基本概念 二、图的存储结构 2.1、存储结构 2.1、邻接矩阵(考察重点) 2.1.1、代码实现 2.2、邻接表 2.3.1、无向邻接表存储 2.3.2、有向图邻接表存储 3.1、图的广度优先遍历(层序遍历) 3.2、图的深度优先遍历 本章主要讲的是图的基本概念以及应用,面试

    2024年02月08日
    浏览(51)
  • 图的二种遍历-广度优先遍历和深度优先遍历

    1.树的广度优先遍历 这样一个图中,是如何实现广度优先遍历的呢,首先,从1遍历完成之后,在去遍历2,3,4,最后遍历5 ,6 , 7  , 8。这也就是为什么叫做广度优先遍历,是一层一层的往广的遍历 不存在“回路”,搜索相邻的结点时,不可能搜到已经访问过的结点 树的广度优

    2024年02月02日
    浏览(50)
  • 图的遍历 —— 广度优先遍历

    与树的遍历类似,图的遍历指从图的某一节点出发,按照某种搜索方式对图中的所有节点都仅访问一次。图的遍历可以解决很多搜索问题,实际应用非常广泛。图的遍历根据搜索方式的不同,分为广度优先遍历和深度优先遍历。 图的遍历 —— 广度优先遍历 广度优先搜索(

    2023年04月25日
    浏览(58)
  • 图的遍历(广度优先遍历BFS,深度优先遍历DFS)

    目录 图的遍历概念: 图的广度优先遍历(BFS): 代码实现如下: 测试如下: 注意: 图的深度优先遍历(DFS): 代码实现如下: 测试如下: 总代码: 结语: 给定一个图G和其中任意一个顶点v0,从v0出发,沿着图中各边访问图中的所有顶点,且每个顶点仅被遍历一次。\\\"遍

    2024年02月21日
    浏览(56)
  • 图的遍历-深度优先遍历与广度优先遍历(C语言)

    图的遍历 概念:指的是从图中的任一顶点出发,对图中的所有顶点访问一次且只访问一次。 邻接矩阵及邻接表的创建 : 图的存储结构-无向邻接矩阵与无向邻接表(C语言). 结构定义 邻接矩阵的深度优先遍历操作 邻接矩阵的深度优先递归算法 结构定义 邻接表的深度优先遍

    2024年02月06日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包