Java 由浅入深带你掌握图的遍历
作者:〖雪月清〗 发布时间:2022-05-21 07:21:44
标签: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);
}
来源:https://blog.csdn.net/qq_52595134/article/details/123108852
0
投稿
猜你喜欢
- 1 框架组成SpringSpringMVCMyBatis2 所需工具Mysql 8.0.15数据库管理系统,创建数据库Tomcat 8.5.
- 在项目中遇到try...catch...语句,因为对Java异常处理机制的流程不是很清楚,导致对相关逻辑代码不理解。所以现在来总结Java异
- 前言我在以往的文章中曾介绍过如何给Word文档添加文本水印和图片水印,及怎样删除文档中的水印。关于文本水印,之前那篇教程里主要指的是单行字体
- Java环境部署下载所需软件和依赖安装 jdk路径可选别的盘。但是指向时得注意我自己时装在 F 盘的,在f盘里新建文件夹 Java,Java
- Java常用API介绍API概念什么是API?API(Application Programming interface) 应用程序编程接口
- 1.依赖的jar文件 jsch-0.1.53.jar2.登录方式有密码登录,和密匙登录 代码:主函数:import java.ut
- JetBrains 系列产品(IDEA、Pycharm 等)使用本站破解教程 (opens new window),在输入激活码时,部分小伙
- 平时用到的库仓库名地址备注mavenCentralhttps://repo1.maven.org/maven2/
- 一、目的本篇文章的目的是记录本人使用flutter加载与调用第三方aar包。二、背景本人go后端,业余时间喜欢玩玩flutter。一直有一个
- spinner组件有点类型于HTML中的下拉框<Select></select>的样子,让用户每次从下拉框中选取一个
- 在IDEA中配置log4j,步骤很简单1.在Maven中加入以下配置<dependency> <groupI
- 茫茫人海千千万万,感谢这一秒你看到这里。希望我的面试题系列能对你的有所帮助!共勉!愿你在未来的日子,保持热爱,奔赴山海!Java基础知识(继
- 一. 安装依赖包yum install -y wgetyum install -y gcc-c++yum install -y zlib-d
- 1.docker安装seata 1.3.0镜像docker pull seataio/seata-server:1.3.02.运行容器获取配
- 本文实例讲述了Java Swing实现让窗体居中显示的方法。分享给大家供大家参考,具体如下:Swing组件是AWT组建的增强组件,是功能强大
- 在Android中,线程内部或者线程之间进行信息交互时经常会使用消息,这些基础的东西如果我们熟悉其内部的原理,将会使我们容易、更好地架构系统
- 在开发中,用到springboot项目,当打包后部署运行时,出现了这个问题,网上搜了好多,又是加META-INF配置,又是加啥的,感觉spr
- mybatis foreach嵌套if标签代码实现:Mapper.java文件List<Map<String, Object&g
- 问题springboot 集成springcloud时常常由于版本问题而报错,如下:com.sun.jersey.api.client.Cl
- 1.内部类概念及分类将一个类定义在另一个类的内部或者接口内部或者方法体内部,这个类就被称为内部类,我们不妨将内部类所在的类称为外围类,除了定