Java 由淺入深帶你掌握?qǐng)D的遍歷

更新時(shí)間：2022年03月26日 16:47:02 作者：〖雪月清〗

圖的遍歷是指，從給定圖中任意指定的頂點(diǎn)（稱為初始點(diǎn)）出發(fā)，按照某種搜索方法沿著圖的邊訪問圖中的所有頂點(diǎn)，使每個(gè)頂點(diǎn)僅被訪問一次，這個(gè)過程稱為圖的遍歷。遍歷過程中得到的頂點(diǎn)序列稱為圖遍歷序列

1.圖的遍歷

從圖中某一頂點(diǎn)出發(fā)訪問圖中其余頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問一次

圖的遍歷有兩種深度優(yōu)先遍歷DFS、廣度優(yōu)先遍歷BFS

2.深度優(yōu)先遍歷

深度優(yōu)先遍歷以深度為優(yōu)先進(jìn)行遍歷，簡(jiǎn)單來說就是每次走到底。類似于二叉樹的前序遍歷

思路：

1.以某一個(gè)頂點(diǎn)為起點(diǎn)進(jìn)行深度優(yōu)先遍歷，并標(biāo)記該頂點(diǎn)已訪問

2.以該頂點(diǎn)為起點(diǎn)選取任意一條路徑一直遍歷到底，并標(biāo)記訪問過的頂點(diǎn)

3.第2步遍歷到底后回退到上一個(gè)頂點(diǎn)，重復(fù)第2步

4.遍歷所有頂點(diǎn)結(jié)束

根據(jù)遍歷思路可知，這是一個(gè)遞歸的過程，其實(shí)DFS與回溯基本相同。

遍歷：

以此圖為例進(jìn)行深度優(yōu)先遍歷

	static void dfs(int[][] graph,int idx,boolean[]visit) {
		int len = graph.length;
		//訪問過
	 if(visit[idx]) return;
	 //訪問該頂點(diǎn)
	 System.out.println("V"+idx);
	 //標(biāo)志頂點(diǎn)
	 visit[idx] = true;
	 for(int i = 1;i < len;i++) {
	 //訪問該頂點(diǎn)相連的所有邊
		 if(graph[idx][i] == 1) {
	 //遞歸進(jìn)行dfs遍歷
		 dfs(graph, i, visit);
		 }
	 }
			
	}

遍歷結(jié)果：

V1

V2

V3

V4

V5

V6

V7

V8

V9

創(chuàng)建圖的代碼：

public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		//頂點(diǎn)數(shù) 以1開始
		int n = scanner.nextInt();
		int[][] graph = new int[n+1][n+1];
		//邊數(shù)
		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;
		}
		
		//標(biāo)記數(shù)組 false表示未訪問過 
		boolean[] visit = new boolean[n+1];
		dfs(graph, 1, visit);
		
	}

3.利用DFS判斷有向圖是否存在環(huán)

思路：遍歷某一個(gè)頂點(diǎn)時(shí)，如果除了上一個(gè)頂點(diǎn)之外，還存在其他相連頂點(diǎn)被訪問過，則必然存在環(huán)

	//默認(rèn)無環(huán)
   static boolean flag = false;
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		//頂點(diǎn)數(shù) 以1開始
		int n = scanner.nextInt();
		int[][] graph = new int[n+1][n+1];
		//邊數(shù)
		int m = scanner.nextInt();
		
		for(int i = 1;i <= m;i++) {
			int v1 = scanner.nextInt();
			int v2 = scanner.nextInt();
			graph[v1][v2] = 1;
			
		}
	 //標(biāo)記數(shù)組 true為訪問過
		boolean[] visit = new boolean[n+1];
		dfs(graph, 1, visit,1);
		if(flag) 
			System.out.println("有環(huán)");
		
	}
	
	static void dfs(int[][] graph,int idx,boolean[]visit,int parent) {
		int len = graph.length;
	
	 System.out.println("V"+idx);
	 //標(biāo)記頂點(diǎn)
	 visit[idx] = true;
	 for(int i = 1;i < len;i++) {
		 //訪問該頂點(diǎn)相連的所有邊
		 if(graph[idx][i] == 1) {
		 if( !visit[i] ) {
		 dfs(graph, i, visit,idx);
		 }
		 else if(idx != i) {
			 flag = true;
		 }
		 }
	 }
	
	 
	}

注意：是有向圖判斷是否存在環(huán)，無向圖判斷是否存在環(huán)無意義，因?yàn)槿我鈨蓚€(gè)存在路徑的頂點(diǎn)都可以是環(huán)

4.廣度優(yōu)先遍歷

廣度優(yōu)先遍歷是以廣度（寬度）為優(yōu)先進(jìn)行遍歷。類似于二叉樹的層序遍歷

思路：

1.以某一個(gè)頂點(diǎn)為起點(diǎn)進(jìn)行廣度優(yōu)先遍歷，并標(biāo)記該頂點(diǎn)已訪問

2.訪問所有與該頂點(diǎn)相連且未被訪問過的頂點(diǎn)，并標(biāo)記訪問過的頂點(diǎn)

3.以第2步訪問所得頂點(diǎn)為起點(diǎn)重復(fù)1、2步驟

4.遍歷所有頂點(diǎn)結(jié)束

通過隊(duì)列來輔助遍歷，隊(duì)列出隊(duì)順序即是廣度優(yōu)先遍歷結(jié)果

遍歷

以此圖為例，采用鄰接矩陣的方式創(chuàng)建圖，進(jìn)行BFS遍歷

	static void bfs(int[][] graph) {		
		int len = graph.length;
		//標(biāo)記數(shù)組 false表示未訪問過 
		boolean[] visit = new boolean[len];
		//輔助隊(duì)列
		Queue<Integer> queue = new LinkedList<>();
		
		queue.offer(1);
		visit[1] = true;
		
		while(!queue.isEmpty()) {
			int num = queue.poll();
			System.out.println("V"+num);
					
			//遍歷該頂點(diǎn)所有相連頂點(diǎn)
			for(int i = 1;i < len;i++) {
				//相連并且沒有被訪問過
				if(graph[num][i] == 1 && !visit[i]) {
					queue.offer(i);
					visit[i] = true;				
				}
			}
		}	
	}

遍歷結(jié)果：

V1

V2

V6

V3

V7

V9

V5

V4

V8

創(chuàng)建圖的代碼

public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		//頂點(diǎn)數(shù) 以1開始
		int n = scanner.nextInt();
		int[][] graph = new int[n+1][n+1];
		//邊數(shù)
		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);
	}

到此這篇關(guān)于Java 由淺入深帶你掌握?qǐng)D的遍歷的文章就介紹到這了,更多相關(guān)Java 圖的遍歷內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: