Java 由浅入深带你掌握图的遍历
1.图的遍历
从图中某一顶点出发访问图中其余顶点,且每个顶点仅被访问一次
图的遍历有两种深度优先遍历DFS、广度优先遍历BFS
2.深度优先遍历
深度优先遍历以深度为优先进行遍历,简单来说就是每次走到底。类似于二叉树的前序遍历
思路:
1.以某一个顶点为起点进行深度优先遍历,并标记该顶点已访问
2.以该顶点为起点选取任意一条路径一直遍历到底,并标记访问过的顶点
3.第2步遍历到底后回退到上一个顶点,重复第2步
4.遍历所有顶点结束
根据遍历思路可知,这是一个递归的过程,其实DFS与回溯基本相同。
遍历:
以此图为例进行深度优先遍历
static void dfs(int[][] graph,int idx,boolean[]visit) { int len = graph.length; //访问过 if(visit[idx]) return; //访问该顶点 System.out.println("V"+idx); //标志顶点 visit[idx] = true; for(int i = 1;i < len;i++) { //访问该顶点相连的所有边 if(graph[idx][i] == 1) { //递归进行dfs遍历 dfs(graph, i, visit); } } }
遍历结果:
V1
V2
V3
V4
V5
V6
V7
V8
V9
创建图的代码:
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); //顶点数 以1开始 int n = scanner.nextInt(); int[][] graph = new int[n+1][n+1]; //边数 int m = scanner.nextInt(); for(int i = 1;i <= m;i++) { int v1 = scanner.nextInt(); int v2 = scanner.nextInt(); graph[v1][v2] = 1; graph[v2][v1] = 1; } //标记数组 false表示未访问过 boolean[] visit = new boolean[n+1]; dfs(graph, 1, visit); }
3.利用DFS判断有向图是否存在环
思路:遍历某一个顶点时,如果除了上一个顶点之外,还存在其他相连顶点被访问过,则必然存在环
//默认无环 static boolean flag = false; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); //顶点数 以1开始 int n = scanner.nextInt(); int[][] graph = new int[n+1][n+1]; //边数 int m = scanner.nextInt(); for(int i = 1;i <= m;i++) { int v1 = scanner.nextInt(); int v2 = scanner.nextInt(); graph[v1][v2] = 1; } //标记数组 true为访问过 boolean[] visit = new boolean[n+1]; dfs(graph, 1, visit,1); if(flag) System.out.println("有环"); } static void dfs(int[][] graph,int idx,boolean[]visit,int parent) { int len = graph.length; System.out.println("V"+idx); //标记顶点 visit[idx] = true; for(int i = 1;i < len;i++) { //访问该顶点相连的所有边 if(graph[idx][i] == 1) { if( !visit[i] ) { dfs(graph, i, visit,idx); } else if(idx != i) { flag = true; } } } }
注意:是有向图判断是否存在环,无向图判断是否存在环无意义,因为任意两个存在路径的顶点都可以是环
4.广度优先遍历
广度优先遍历是以广度(宽度)为优先进行遍历。类似于二叉树的层序遍历
思路:
1.以某一个顶点为起点进行广度优先遍历,并标记该顶点已访问
2.访问所有与该顶点相连且未被访问过的顶点,并标记访问过的顶点
3.以第2步访问所得顶点为起点重复1、2步骤
4.遍历所有顶点结束
通过队列来辅助遍历,队列出队顺序即是广度优先遍历结果
遍历
以此图为例,采用邻接矩阵的方式创建图,进行BFS遍历
static void bfs(int[][] graph) { int len = graph.length; //标记数组 false表示未访问过 boolean[] visit = new boolean[len]; //辅助队列 Queue<Integer> queue = new LinkedList<>(); queue.offer(1); visit[1] = true; while(!queue.isEmpty()) { int num = queue.poll(); System.out.println("V"+num); //遍历该顶点所有相连顶点 for(int i = 1;i < len;i++) { //相连并且没有被访问过 if(graph[num][i] == 1 && !visit[i]) { queue.offer(i); visit[i] = true; } } } }
遍历结果:
V1
V2
V6
V3
V7
V9
V5
V4
V8
创建图的代码
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); //顶点数 以1开始 int n = scanner.nextInt(); int[][] graph = new int[n+1][n+1]; //边数 int m = scanner.nextInt(); for(int i = 1;i <= m;i++) { int v1 = scanner.nextInt(); int v2 = scanner.nextInt(); graph[v1][v2] = 1; graph[v2][v1] = 1; } bfs(graph); }
到此这篇关于Java 由浅入深带你掌握图的遍历的文章就介绍到这了,更多相关Java 图的遍历内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/qq_52595134/article/details/123108852
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20- 这篇文章主要介绍了Java线程池中的各个参数如何合理设置操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-06-19
- 在Java中,我们可以利用多线程来最大化地压榨CPU多核计算的能力,下面这篇文章主要给大家介绍了关于java中多线程与线程池基本使用的相关资料,需要的朋友可以参考下...2021-09-13