图的dfs遍历和bfs遍历

📑前言

本文主要是【图的dfs遍历和bfs遍历】——图遍历的文章，如果有什么需要改进的地方还请大佬指出??

🎬作者简介：大家好，我是听风与他🥇
??博客首页：CSDN主页听风与他
🌄每日一句：狠狠沉淀，顶峰相见

图的dfs遍历和bfs遍历

• 以如下的无向图为例

package 图论;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 图的dfs和bfs实现 {
/* 8个顶点，9条边
8 9
0 1
0 2
1 3
1 4
1 5
3 4
2 6
2 7
6 7
 */
	static int n=0,m=0;//n个顶点,m条边
	static int[][] g;//用来做邻接矩阵
	static int[] visit;//用来记录哪些边已经被访问了
	static int vcount=0;//记录已经访问过多少个结点
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		g = new int[n][n];
		visit = new int[n];
		for(int i=0;i<m;i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			g[from][to]=1;
			g[to][from]=1;//无向图，双方都可到达，矩阵关于对角线对称
		}
//		for(int[] x:g) {
//			System.out.println(Arrays.toString(x));
//		}
//		visit[0]=1;//标记为已访问
//		gdfs(0);
		gbfs();
	}
	
	public static void gdfs(int nownode) {
		System.out.println(nownode+"->");
		vcount++;//表示已经访问的顶点个数+1
		if (vcount==n) {
			return;//dfs出口
		}
		for(int i=0;i<n;i++) {//n个相邻的顶点全部跑一边，没有访问过的，而且挨着才能开枝散叶
			if (g[nownode][i]==1 && visit[i]==0) {//联通且没有被访问
				visit[i]=1;//表示顶点已经被访问
				gdfs(i);
			}
		}
	}
	
	public static void gbfs() {
		Queue<Integer> q = new LinkedList<>();
		q.offer(0);//默认从0开始
		visit[0]=1;//标记0结点已经被访问
		while(!q.isEmpty()) {
			int head = q.poll();//弹出列头
			System.out.println(head+"->");
			for(int i=0;i<n;i++) {
				if(g[head][i]==1 && visit[i]==0) {
					q.offer(i);
					visit[i]=1;//这个顶点已经入列，表示被访问
				}
			}
		}
	}

}

打印结果:

//dfs:	0->1->3->4->5->2->6->7->
//bfs:	0->1->2->3->4->5->6->7->

📑文章末尾