运维开发网

Java带你从简单到深入地遍历图形

运维开发网 https://www.qedev.com 2022-04-28 17:01 出处:网络
图的遍历是指,从给定图中任意指定的顶点(称为初始点)出发,按照某种搜索方法沿着图的边访问图中的所有顶点,使每个顶点仅被访问一次,这个过程称为图的遍历。遍历过程中得到的顶点序列称为图遍历序列

图的遍历是指,从给定图中任意指定的顶点(称为初始点)出发,按照某种搜索方法沿着图的边访问图中的所有顶点,使每个顶点仅被访问一次,这个过程称为图的遍历。遍历过程中得到的顶点序列称为图遍历序列


1.图的遍历

从图中的一个顶点开始,访问图中的其他顶点,每个顶点只访问一次。

图的遍历有两种:深度优先遍历DFS和广度优先遍历BFS。


2.深度优先遍历

深度优先遍历以深度为优先级,简单来说就是每次都走到最后。类似二叉树的前序遍历

想法:

1.以一个顶点为起点先遍历深度,标记该顶点已经被访问过。

2.以顶点为起点,选择任意一条路径遍历到终点,标记访问过的顶点。

3.第二步:遍历到终点后回到上一个顶点,重复第二步。

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 lt; len;i++) { //访问该顶点相连的所有边 if(graph[idx][i] == 1) { //递归进行dfs遍历 dfs(graph, i, visit); } }}

遍历结果:

第五颅神经的眼支

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 lt;= 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 lt;= 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 lt; 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];//辅助队列Queuelt;Integergt; queue = new LinkedListlt;gt;();queue.offer(1);visit[1] = true;while(!queue.isEmpty()) {int num = queue.poll();System.out.println("V"+num);//遍历该顶点所有相连顶点for(int i = 1;i lt; len;i++) {//相连并且没有被访问过if(graph[num][i] == 1 amp;amp; !visit[i]) {queue.offer(i);visit[i] = true;}}}}

遍历结果:

第五颅神经的眼支

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 lt;= m;i++) {int v1 = scanner.nextInt();int v2 = scanner.nextInt();graph[v1][v2] = 1;graph[v2][v1] = 1;}bfs(graph);}

这就是这篇关于Java从简单到深入的文章,它向您展示了如何掌握Java图的遍历。关于Java图遍历的更多信息,请搜索源搜网之前的文章或者继续浏览下面的相关文章。希望大家以后能多支持源搜网!


0

精彩评论

暂无评论...
验证码 换一张
取 消