資料結構–圖（深度優先遍歷和廣度優先遍歷）（Java）-有解無憂

資料結構–圖（深度優先遍歷和廣度優先遍歷）（Java）

博客說明

文章所涉及的資料來自互聯網整理和個人總結，意在于個人學習和經驗匯總，如有什么地方侵權，請聯系本人洗掉，謝謝！

圖的常用概念

圖是一種資料結構，其中結點可以具有零個或多個相鄰元素，兩個結點之間的連接稱為邊，結點也可以稱為頂點，

頂點(vertex)
邊(edge)
路徑
無向圖

有向圖

帶權圖

圖的表示方式

圖的表示方式有兩種：二維陣串列示（鄰接矩陣）；鏈表表示（鄰接表），

鄰接矩陣

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

鄰接表

鄰接矩陣需要為每個頂點都分配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);
		}
		
		//插入圖的節點
		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("廣度優先遍歷
		graph.dfs(); 
		System.out.println("深度優先遍歷
		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;
	}
	
	//深度優先遍歷
	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);
			}
		}
	}
	
	//廣度優先遍歷
	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);
	}
	
  //插入權值
	public void insertEdge(int v1, int v2, int weight) {
		edges[v1][v2] = weight;
		edges[v2][v1] = weight;
		numOfEdges++;
	}
}

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

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

演算法

訪問初始結點v，并標記結點v為已訪問，
查找結點v的第一個鄰接結點w，
若w存在，則繼續執行4，如果w不存在，則回到第1步，將從v的下一個結點繼續，
若w未被訪問，對w進行深度優先遍歷遞回（即把w當做另一個v，然后進行步驟123），
查找結點v的w鄰接結點的下一個鄰接結點，轉到步驟3

代碼

//深度優先遍歷
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);
    }
  }
}

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

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

演算法

訪問初始結點v并標記結點v為已訪問，
結點v入佇列
當佇列非空時，繼續執行，否則演算法結束，
出佇列，取得隊頭結點u，
查找結點u的第一個鄰接結點w，
若結點u的鄰接結點w不存在，則轉到步驟3；否則回圈執行以下三個步驟：
- 若結點w尚未被訪問，則訪問結點w并標記為已訪問，
- 結點w入佇列
- 查找結點u的繼w鄰接結點后的下一個鄰接結點w，轉到步驟6

代碼

//廣度優先遍歷
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);
    }
  }
}

感謝

尚硅谷

以及勤勞的自己，個人博客，GitHub

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/10035.html

標籤：Java

上一篇：用IDEA一年了，終于敢說自己會用了

下一篇：LeetCode–二叉樹的所有路徑