數(shù)據(jù)結(jié)構(gòu)–圖（深度優(yōu)先遍歷和廣度優(yōu)先遍歷）（Java）
博客說明
文章所涉及的資料來自互聯(lián)網(wǎng)整理和個(gè)人總結(jié)朽缴，意在于個(gè)人學(xué)習(xí)和經(jīng)驗(yàn)匯總五续，如有什么地方侵權(quán)，請(qǐng)聯(lián)系本人刪除樊卓，謝謝！
圖的常用概念
圖是一種數(shù)據(jù)結(jié)構(gòu)杠河，其中結(jié)點(diǎn)可以具有零個(gè)或多個(gè)相鄰元素碌尔。兩個(gè)結(jié)點(diǎn)之間的連接稱為邊。 結(jié)點(diǎn)也可以稱為頂點(diǎn)券敌。
- 頂點(diǎn)(vertex)
- 邊(edge)
- 路徑
- 無向圖
image-20200904124205865
- 有向圖
image-20200904124318805
- 帶權(quán)圖
image-20200904124332489
圖的表示方式
圖的表示方式有兩種：二維數(shù)組表示（鄰接矩陣）唾戚；鏈表表示（鄰接表）。
鄰接矩陣
鄰接矩陣是表示圖形中頂點(diǎn)之間相鄰關(guān)系的矩陣待诅，對(duì)于n個(gè)頂點(diǎn)的圖而言叹坦，矩陣是的row和col表示的是1....n個(gè)點(diǎn)。
image-20200904124501028
鄰接表
鄰接矩陣需要為每個(gè)頂點(diǎn)都分配n個(gè)邊的空間卑雁，其實(shí)有很多邊都是不存在,會(huì)造成空間的一定損失
鄰接表的實(shí)現(xiàn)只關(guān)心存在的邊募书，不關(guān)心不存在的邊轧钓。因此沒有空間浪費(fèi)，鄰接表由數(shù)組+鏈表組成
image-20200904124627030
代碼實(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é)點(diǎn)
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é)點(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)， 可以這樣理解：每次都在訪問完當(dāng)前結(jié)點(diǎn)后首先訪問當(dāng)前結(jié)點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)
算法
- 訪問初始結(jié)點(diǎn)v荷逞，并標(biāo)記結(jié)點(diǎn)v為已訪問媒咳。
- 查找結(jié)點(diǎn)v的第一個(gè)鄰接結(jié)點(diǎn)w。
- 若w存在种远，則繼續(xù)執(zhí)行4涩澡，如果w不存在，則回到第1步坠敷，將從v的下一個(gè)結(jié)點(diǎn)繼續(xù)妙同。
- 若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)先遍歷
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)
類似于一個(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è)步驟：
- 若結(jié)點(diǎn)w尚未被訪問，則訪問結(jié)點(diǎn)w并標(biāo)記為已訪問鸯两。
- 結(jié)點(diǎn)w入隊(duì)列
- 查找結(jié)點(diǎn)u的繼w鄰接結(jié)點(diǎn)后的下一個(gè)鄰接結(jié)點(diǎn)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);
}
}
}
感謝
尚硅谷
微信公眾號(hào)
