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

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

圖的常用概念

圖是一種數(shù)據(jù)結(jié)構(gòu)，其中結(jié)點可以具有零個或多個相鄰元素。兩個結(jié)點之間的連接稱為邊。 結(jié)點也可以稱為頂點。

• 頂點(vertex)

• 邊(edge)

• 路徑

• 無向圖

• 有向圖

• 帶權(quán)圖

圖的表示方式

圖的表示方式有兩種：二維數(shù)組表示（鄰接矩陣）；鏈表表示（鄰接表）。

鄰接矩陣

鄰接矩陣是表示圖形中頂點之間相鄰關(guān)系的矩陣，對于n個頂點的圖而言，矩陣是的row和col表示的是1....n個點。

鄰接表

鄰接矩陣需要為每個頂點都分配n個邊的空間，其實有很多邊都是不存在,會造成空間的一定損失

鄰接表的實現(xiàn)只關(guān)心存在的邊，不關(guān)心不存在的邊。因此沒有空間浪費，鄰接表由數(shù)組+鏈表組成

代碼實現(xiàn)

package com.guizimo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Graph {

	private ArrayList<String> vertexList; 
	private int[][] edges; 
	private int numOfEdges; 
	private boolean[] isVisited;
	
	public static void main(String[] args) {

		int n = 8;
		String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
		Graph graph = new Graph(n);
		for(String vertex: Vertexs) {
			graph.insertVertex(vertex);
		}
		
		//插入圖的節(jié)點
		graph.insertEdge(0, 1, 1);
		graph.insertEdge(0, 2, 1);
		graph.insertEdge(1, 3, 1);
		graph.insertEdge(1, 4, 1);
		graph.insertEdge(3, 7, 1);
		graph.insertEdge(4, 7, 1);
		graph.insertEdge(2, 5, 1);
		graph.insertEdge(2, 6, 1);
		graph.insertEdge(5, 6, 1);

		//遍歷圖
		graph.showGraph();
		
		System.out.println("廣度優(yōu)先遍歷
		graph.dfs(); 
		System.out.println("深度優(yōu)先遍歷
		graph.bfs();
		
	}
	
	public Graph(int n) {
		edges = new int[n][n];
		vertexList = new ArrayList<String>(n);
		numOfEdges = 0;
	}
	

	public int getFirstNeighbor(int index) {
		for(int j = 0; j < vertexList.size(); j++) {
			if(edges[index][j] > 0) {
				return j;
			}
		}
		return -1;
	}

	public int getNextNeighbor(int v1, int v2) {
		for(int j = v2 + 1; j < vertexList.size(); j++) {
			if(edges[v1][j] > 0) {
				return j;
			}
		}
		return -1;
	}
	
	//深度優(yōu)先遍歷
	private void dfs(boolean[] isVisited, int i) {
		System.out.print(getValueByIndex(i) + "->");
		isVisited[i] = true;
		int w = getFirstNeighbor(i);
		while(w != -1) {
			if(!isVisited[w]) {
				dfs(isVisited, w);
			}
			w = getNextNeighbor(i, w);
		}
		
	}
	
	public void dfs() {
		isVisited = new boolean[vertexList.size()];
		for(int i = 0; i < getNumOfVertex(); i++) {
			if(!isVisited[i]) {
				dfs(isVisited, i);
			}
		}
	}
	
	//廣度優(yōu)先遍歷
	private void bfs(boolean[] isVisited, int i) {
		int u ; 
		int w ; 
		LinkedList queue = new LinkedList();
		System.out.print(getValueByIndex(i) + "=>");
		isVisited[i] = true;
		queue.addLast(i);
		
		while( !queue.isEmpty()) {
			u = (Integer)queue.removeFirst();
			w = getFirstNeighbor(u);
			while(w != -1) {
				if(!isVisited[w]) {
					System.out.print(getValueByIndex(w) + "=>");
					isVisited[w] = true;
					queue.addLast(w);
				}
				w = getNextNeighbor(u, w); 
			}
		}
		
	} 
	
	public void bfs() {
		isVisited = new boolean[vertexList.size()];
		for(int i = 0; i < getNumOfVertex(); i++) {
			if(!isVisited[i]) {
				bfs(isVisited, i);
			}
		}
	}
	
	public int getNumOfVertex() {
		return vertexList.size();
	}
                       
	//遍歷
	public void showGraph() {
		for(int[] link : edges) {
			System.err.println(Arrays.toString(link));
		}
	}
                       
	public int getNumOfEdges() {
		return numOfEdges;
	}

	public String getValueByIndex(int i) {
		return vertexList.get(i);
	}
                       
	public int getWeight(int v1, int v2) {
		return edges[v1][v2];
	}
                       
	//添加鄰接矩陣
	public void insertVertex(String vertex) {
		vertexList.add(vertex);
	}
	
  //插入權(quán)值
	public void insertEdge(int v1, int v2, int weight) {
		edges[v1][v2] = weight;
		edges[v2][v1] = weight;
		numOfEdges++;
	}
}

圖的深度優(yōu)先搜索(Depth First Search)

深度優(yōu)先遍歷，從初始訪問結(jié)點出發(fā)，初始訪問結(jié)點可能有多個鄰接結(jié)點，深度優(yōu)先遍歷的策略就是首先訪問第一個鄰接結(jié)點，然后再以這個被訪問的鄰接結(jié)點作為初始結(jié)點，訪問它的第一個鄰接結(jié)點， 可以這樣理解：每次都在訪問完當(dāng)前結(jié)點后首先訪問當(dāng)前結(jié)點的第一個鄰接結(jié)點

算法

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

• 查找結(jié)點v的第一個鄰接結(jié)點w。

• 若w存在，則繼續(xù)執(zhí)行4，如果w不存在，則回到第1步，將從v的下一個結(jié)點繼續(xù)。

• 若w未被訪問，對w進行深度優(yōu)先遍歷遞歸（即把w當(dāng)做另一個v，然后進行步驟123）。

• 查找結(jié)點v的w鄰接結(jié)點的下一個鄰接結(jié)點，轉(zhuǎn)到步驟3

代碼

//深度優(yōu)先遍歷
private void dfs(boolean[] isVisited, int i) {
  System.out.print(getValueByIndex(i) + "->");
  isVisited[i] = true;
  int w = getFirstNeighbor(i);
  while(w != -1) {
    if(!isVisited[w]) {
      dfs(isVisited, w);
    }
    w = getNextNeighbor(i, w);
  }

}

public void dfs() {
  isVisited = new boolean[vertexList.size()];
  for(int i = 0; i < getNumOfVertex(); i++) {
    if(!isVisited[i]) {
      dfs(isVisited, i);
    }
  }
}

圖的廣度優(yōu)先搜索(Broad First Search)

類似于一個分層搜索的過程，廣度優(yōu)先遍歷需要使用一個隊列以保持訪問過的結(jié)點的順序，以便按這個順序來訪問這些結(jié)點的鄰接結(jié)點

算法

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

• 結(jié)點v入隊列

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

• 出隊列，取得隊頭結(jié)點u。

• 查找結(jié)點u的第一個鄰接結(jié)點w。

• 若結(jié)點u的鄰接結(jié)點w不存在，則轉(zhuǎn)到步驟3；否則循環(huán)執(zhí)行以下三個步驟：

• 若結(jié)點w尚未被訪問，則訪問結(jié)點w并標(biāo)記為已訪問。

• 結(jié)點w入隊列

• 查找結(jié)點u的繼w鄰接結(jié)點后的下一個鄰接結(jié)點w，轉(zhuǎn)到步驟6

代碼

//廣度優(yōu)先遍歷
private void bfs(boolean[] isVisited, int i) {
  int u ; 
  int w ; 
  LinkedList queue = new LinkedList();
  System.out.print(getValueByIndex(i) + "=>");
  isVisited[i] = true;
  queue.addLast(i);

  while( !queue.isEmpty()) {
    u = (Integer)queue.removeFirst();
    w = getFirstNeighbor(u);
    while(w != -1) {
      if(!isVisited[w]) {
        System.out.print(getValueByIndex(w) + "=>");
        isVisited[w] = true;
        queue.addLast(w);
      }
      w = getNextNeighbor(u, w); 
    }
  }

} 

public void bfs() {
  isVisited = new boolean[vertexList.size()];
  for(int i = 0; i < getNumOfVertex(); i++) {
    if(!isVisited[i]) {
      bfs(isVisited, i);
    }
  }
}

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