第Java由淺入深帶你掌握圖的遍歷目錄1.圖的遍歷2.深度優(yōu)先遍歷3.利用DFS判斷有向圖是否存在環(huán)4.廣度優(yōu)先遍歷

1.圖的遍歷

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

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

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

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

思路：

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

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

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

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

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

遍歷：

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

staticvoiddfs(int[][]graph,intidx,boolean[]visit){

intlen=graph.length;

//訪問過

if(visit[idx])return;

//訪問該頂點

System.out.println("V"+idx);

//標(biāo)志頂點

visit[idx]=true;

for(inti=1;ilen;i++){

//訪問該頂點相連的所有邊

if(graph[idx][i]==1){

//遞歸進(jìn)行dfs遍歷

dfs(graph,i,visit);

}

遍歷結(jié)果：

V1

V2

V3

V4

V5

V6

V7

V8

V9

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

publicstaticvoidmain(String[]args){

Scannerscanner=newScanner(System.in);

//頂點數(shù)以1開始

intn=scanner.nextInt();

int[][]graph=newint[n+1][n+1];

//邊數(shù)

intm=scanner.nextInt();

for(inti=1;ii++){

intv1=scanner.nextInt();

intv2=scanner.nextInt();

graph[v1][v2]=1;

graph[v2][v1]=1;

//標(biāo)記數(shù)組false表示未訪問過

boolean[]visit=newboolean[n+1];

dfs(graph,1,visit);

}

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

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

//默認(rèn)無環(huán)

staticbooleanflag=false;

publicstaticvoidmain(String[]args){

Scannerscanner=newScanner(System.in);

//頂點數(shù)以1開始

intn=scanner.nextInt();

int[][]graph=newint[n+1][n+1];

//邊數(shù)

intm=scanner.nextInt();

for(inti=1;ii++){

intv1=scanner.nextInt();

intv2=scanner.nextInt();

graph[v1][v2]=1;

//標(biāo)記數(shù)組true為訪問過

boolean[]visit=newboolean[n+1];

dfs(graph,1,visit,1);

if(flag)

System.out.println("有環(huán)");

staticvoiddfs(int[][]graph,intidx,boolean[]visit,intparent){

intlen=graph.length;

System.out.println("V"+idx);

//標(biāo)記頂點

visit[idx]=true;

for(inti=1;ilen;i++){

//訪問該頂點相連的所有邊

if(graph[