Java深度優(yōu)先和廣度優(yōu)先遍歷怎么使用

166次閱讀

共計(jì) 2836 個(gè)字符，預(yù)計(jì)需要花費(fèi) 8 分鐘才能閱讀完成。

這篇文章主要介紹“Java 深度優(yōu)先和廣度優(yōu)先遍歷怎么使用”，在日常操作中，相信很多人在 Java 深度優(yōu)先和廣度優(yōu)先遍歷怎么使用問題上存在疑惑，丸趣 TV 小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”Java 深度優(yōu)先和廣度優(yōu)先遍歷怎么使用”的疑惑有所幫助！接下來，請(qǐng)跟著丸趣 TV 小編一起來學(xué)習(xí)吧！

# 遍歷

圖的遍歷，所謂遍歷，即是對(duì)結(jié)點(diǎn)的訪問。一個(gè)圖有那么多個(gè)結(jié)點(diǎn)，如何遍歷這些結(jié)點(diǎn)，需要特定策略，一般有兩種訪問策略：

深度優(yōu)先遍歷

廣度優(yōu)先遍歷 #深度優(yōu)先

深度優(yōu)先遍歷，從初始訪問結(jié)點(diǎn)出發(fā)，我們知道初始訪問結(jié)點(diǎn)可能有多個(gè)鄰接結(jié)點(diǎn)，深度優(yōu)先遍歷的策略就是首先訪問第一個(gè)鄰接結(jié)點(diǎn)，然后再以這個(gè)被訪問的鄰接結(jié)點(diǎn)作為初始結(jié)點(diǎn)，訪問它的第一個(gè)鄰接結(jié)點(diǎn)?？偨Y(jié)起來可以這樣說：每次都在訪問完當(dāng)前結(jié)點(diǎn)后首先訪問當(dāng)前結(jié)點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)。我們從這里可以看到，這樣的訪問策略是優(yōu)先往縱向挖掘深入，而不是對(duì)一個(gè)結(jié)點(diǎn)的所有鄰接結(jié)點(diǎn)進(jìn)行橫向訪問。具體算法表述如下：

訪問初始結(jié)點(diǎn) v，并標(biāo)記結(jié)點(diǎn) v 為已訪問。

查找結(jié)點(diǎn) v 的第一個(gè)鄰接結(jié)點(diǎn) w。

若 w 存在，則繼續(xù)執(zhí)行 4，否則算法結(jié)束。

若 w 未被訪問，對(duì) w 進(jìn)行深度優(yōu)先遍歷遞歸（即把 w 當(dāng)做另一個(gè) v，然后進(jìn)行步驟 123）。
查找結(jié)點(diǎn) v 的 w 鄰接結(jié)點(diǎn)的下一個(gè)鄰接結(jié)點(diǎn)，轉(zhuǎn)到步驟 3。
例如下圖，其深度優(yōu)先遍歷順序?yàn)?1- 2- 4- 8- 5- 3- 6- 7
#廣度優(yōu)先

類似于一個(gè)分層搜索的過程，廣度優(yōu)先遍歷需要使用一個(gè)隊(duì)列以保持訪問過的結(jié)點(diǎn)的順序，以便按這個(gè)順序來訪問這些結(jié)點(diǎn)的鄰接結(jié)點(diǎn)。具體算法表述如下：

訪問初始結(jié)點(diǎn) v 并標(biāo)記結(jié)點(diǎn) v 為已訪問。

結(jié)點(diǎn) v 入隊(duì)列

當(dāng)隊(duì)列非空時(shí)，繼續(xù)執(zhí)行，否則算法結(jié)束。

出隊(duì)列，取得隊(duì)頭結(jié)點(diǎn) u。

查找結(jié)點(diǎn) u 的第一個(gè)鄰接結(jié)點(diǎn) w。

若結(jié)點(diǎn) u 的鄰接結(jié)點(diǎn) w 不存在，則轉(zhuǎn)到步驟 3；否則循環(huán)執(zhí)行以下三個(gè)步驟：
1). 若結(jié)點(diǎn) w 尚未被訪問，則訪問結(jié)點(diǎn) w 并標(biāo)記為已訪問。
2). 結(jié)點(diǎn) w 入隊(duì)列
3). 查找結(jié)點(diǎn) u 的繼 w 鄰接結(jié)點(diǎn)后的下一個(gè)鄰接結(jié)點(diǎn) w，轉(zhuǎn)到步驟 6。
如下圖，其廣度優(yōu)先算法的遍歷順序?yàn)椋?- 2- 3- 4- 5- 6- 7- 8

package com.lifeibigdata.algorithms.graph.liantongfenliang;
import java.util.LinkedList;
import java.util.Queue;
 * Created by leofei.li on 2016/5/21.
 */
public class BFS {
 static int verNum;
 static boolean []visited;
 static String []ver={ A , B , C , D , E 
 static int [][]edge;
 void addEdge(int i,int j){ if(i == j)return;
 edge[i][j]=1;
 edge[j][i]=1;
 }
 void dfsTraverse(){ visited = new boolean[verNum];
 for(int i = 0; i  verNum; i ++){ if(visited[i] == false){ dfs(i);
 }
 }
 }
 void dfs(int i){ visited[i] = true;
 System.out.print(ver[i] +    
 for(int j = 0; j   verNum; j++){ if(visited[j] == false   edge[i][j] == 1){ dfs(j);
 }
 }
 }
 void bfsTraverse(){ visited = new boolean[verNum];
 Queue Integer  quene = new LinkedList Integer 
 for (int i = 0; i   verNum; i ++){ if(visited[i] == false){ visited[i] = true;
 System.out.print(ver[i]+   
 quene.add(i); // 此處存儲(chǔ)的是索引
 while (!quene.isEmpty()){ // 注意結(jié)束條件
 int j = quene.poll();
 for (int k = 0; k   verNum; k++){ // 找到該節(jié)點(diǎn)所有的子節(jié)點(diǎn)
 if(edge[j][k] == 1   visited[k] == false){ visited[k] = true;
 System.out.print(ver[k]+   
 quene.add(k);
 }
 }
 }
 }
 }
 }
 void con(){
 int count = 0;
 visited = new boolean[verNum];
 for(int i = 0; i   verNum; i ++){ if(!visited[i]){
 count++;
 dfsTraverse();
 }
 }
 System.out.println( 共有 +count+ 個(gè)連通分量! 
 }
 public static void main(String[] args) {
 verNum = ver.length;
 edge = new int[verNum][verNum];
 for(int i=0;i verNum;i++){ for (int j=0;j verNum;j++){ edge[i][j]=0;
 }
 }
 BFS b = new BFS();
 b.addEdge(0, 3);
 b.addEdge(0, 4);
 b.addEdge(1, 2);
 b.addEdge(2, 4);
 b.addEdge(2, 3);
 System.out.println( 圖的深度遍歷操作: 
 b.dfsTraverse();
 System.out.println();
 System.out.println( 圖的廣度遍歷操作： b.bfsTraverse();
 System.out.println();
 System.out.println( 連通分量: 
 b.con();
 }
}

不管深搜還是廣搜都需要申請(qǐng)總節(jié)點(diǎn)個(gè)數(shù)長(zhǎng)度的數(shù)組用來標(biāo)記節(jié)點(diǎn)是否訪問過 (訪問數(shù)組)；深搜是遍歷訪問數(shù)組，從某個(gè)未被訪問的節(jié)點(diǎn)輻射出去，每次輻射結(jié)束后，判斷訪問數(shù)組中是否還有未被訪問的節(jié)點(diǎn)，如果有，再次輻射，如果沒有，深搜結(jié)束；廣搜是同樣是遍歷數(shù)組，判斷是否有為被訪問的節(jié)點(diǎn)，如果有放到對(duì)列中，然后彈出隊(duì)列，將彈出節(jié)點(diǎn)所有未被訪問的鄰接節(jié)點(diǎn)放到隊(duì)列中，繼續(xù)進(jìn)行訪問隊(duì)列，直到隊(duì)列為空時(shí)繼續(xù)判斷訪問數(shù)組

到此，關(guān)于“Java 深度優(yōu)先和廣度優(yōu)先遍歷怎么使用”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注丸趣 TV 網(wǎng)站，丸趣 TV 小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！

正文完