您好,登錄后才能下訂單哦!
本文小編為大家詳細(xì)介紹“Java怎么實(shí)現(xiàn)圖的遍歷”,內(nèi)容詳細(xì),步驟清晰,細(xì)節(jié)處理妥當(dāng),希望這篇“Java怎么實(shí)現(xiàn)圖的遍歷”文章能幫助大家解決疑惑,下面跟著小編的思路慢慢深入,一起來學(xué)習(xí)新知識吧。
從圖中某一頂點(diǎn)出發(fā)訪問圖中其余頂點(diǎn),且每個(gè)頂點(diǎn)僅被訪問一次
圖的遍歷有兩種深度優(yōu)先遍歷DFS、廣度優(yōu)先遍歷BFS
深度優(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步遍歷到底后回退到上一個(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); }
思路:遍歷某一個(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)
廣度優(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); }
讀到這里,這篇“Java怎么實(shí)現(xiàn)圖的遍歷”文章已經(jīng)介紹完畢,想要掌握這篇文章的知識點(diǎn)還需要大家自己動手實(shí)踐使用過才能領(lǐng)會,如果想了解更多相關(guān)內(nèi)容的文章,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。