天天看點
傳回

java實作圖結構以及深度優先搜尋和廣度優先搜尋

    圖結構是資料結構裡面應該是最複雜的一個資料結構，首先是它的實體結構複雜，圖是由頂點和邊組成的，這樣還算是簡單的圖形，另外還有帶權圖。以前的資料結構如：連結清單，樹，棧，隊列等等，基本都可以通過普通的數組和連結清單來建構，但是圖因為組成的元素不僅有頂點，還有邊，是以表示起來會相對複雜一些，一般是通過鄰接矩陣或者矩陣表來表示，如下圖所示的圖，有五個頂點和四個邊組成。

java實作圖結構以及深度優先搜尋和廣度優先搜尋

通過矩陣來表示就如下圖所示：

java實作圖結構以及深度優先搜尋和廣度優先搜尋

    這個矩陣其實隻是通過二維數組表示了頂點與邊之間的關系，當矩陣中數字為1表示兩個頂點之間有邊。另外，我們還需要通過一個數組來表示頂點。

    圖可以解決很多問題，比如最小生成樹，最短路徑，top排序等等，另外圖的搜尋分為兩種，一種是深度優先搜尋，另外一種是廣度優先搜尋，現在來說說他們的具體是怎麼回事。

    先說深度優先搜尋，這是一種周遊圖中所有頂點的一種方式，它遵照以下三種規則：

  • 規則一、如果可能，通路一個相鄰的未通路的節點，标記它，并放入棧中。
  • 規則二、當不能執行規則一時，如果棧不為空，那麼從棧中彈出一個頂點。
  • 規則三、如果不能執行規則一和規則二，就完成了整個搜尋過程。

    整個搜尋周遊過程如下圖所示，順序在圖中已經标出：

java實作圖結構以及深度優先搜尋和廣度優先搜尋

    廣度優先搜尋，它與深度優先搜尋不同的地方在于它是先周遊最靠近初始周遊節點的節點，然後依次周遊離初始節點越來越遠的節點，它也遵照以下三種規則：

  • 規則一、通路下一個未通路的相鄰節點（如果存在），這個頂點必須是目前頂點的鄰接點，标記它，并把它放入隊列中。
  • 規則二、如果因為已經沒有未通路的頂點而不能執行規則一，那麼從隊列頭中取出一個頂點（如果存在），并使它成為目前頂點。
  • 規則三、如果因為隊列為空而不能執行規則二，則搜尋結束。

    廣度優先搜尋周遊過程如下圖所示，順序也在圖中已經标出：

java實作圖結構以及深度優先搜尋和廣度優先搜尋

    兩種搜尋方式通過圖形來表示很直覺，但是實作方式卻是有很大的差别，第一種深度優先搜尋，我們需要借助一個棧，将周遊的節點先放入棧中，并标記已經周遊，如果有相鄰節點也是會存入棧中并标記，如果沒有相鄰節點了，那麼就取出棧中的節點，依次周遊下去，直到棧中元素為空，那麼周遊結束。

    而廣度優先搜尋就不一樣，我們需要按照節點從近到遠的順序來依次周遊，是以需要使用一個隊列，先将頭結點放入隊列，依次周遊他的相鄰節點，标記并放入隊列中，如果節點沒有相鄰節點了，那麼就從隊列頭部取出一個節點，繼續周遊他的相鄰節點，标記并存入隊列，直到隊列為空，周遊結束。

    整個圖結構的表示和周遊需要用到二維數組表示頂點之間的關系，用一維數組表示頂點，需要使用棧來做深度優先的周遊操作，需要使用隊列來做廣度優先的周遊操作，是以表示起來比較複雜。

    按照上面的思路，我們可以實作圖的結構以及周遊，下面給出所有的代碼：

    Vertex.java

package com.xxx.algorithm.wh.graph;
/**
 * 頂點實體
 *
 */
public class Vertex {
	public char label;
	public boolean visited;
	public Vertex(char lab){
		this.label = lab;
		this.visited = false;
	}
}

    StackX.java

package com.xxx.algorithm.wh.graph;

public class StackX {
	private final int SIZE=20;
	private int st[];
	private int top;
	
	public StackX(){
		st = new int[SIZE];
		top=-1;
	}
	
	public void push(int val){
		st[++top] = val;
	}
	
	public int pop(){
		return st[top--];
	}
	
	public int peek(){
		return st[top];
	}
	
	public boolean isEmpty(){
		return top==-1;
	}
	
}

    Queue.java

package com.xxx.algorithm.wh.graph;

public class Queue {
	private final int SIZE=20;
	private int[] queArray;
	private int front;
	private int rear;
	public Queue(){
		queArray = new int[SIZE];
		front = 0;
		rear= -1;
	}
	
	public void insert(int v){
		if(rear==SIZE-1){
			rear = -1;
		}
		queArray[++rear] = v;
	}
	
	public int remove(){
		int temp = queArray[front++];
		if(front==SIZE)
			front = 0;
		return temp;
	}
	
	public boolean isEmpty(){
		return (rear+1==front) || (front+SIZE-1==rear);
	}
}

    Graph.java

package com.xxx.algorithm.wh.graph;

public class Graph {
	private final int MAX_VERTS=20;
	private Vertex vertexList[];
	private int adjMat[][];
	private int nVerts;
	private StackX stack;
	private Queue queue;
	
	public Graph(){
		vertexList = new Vertex[MAX_VERTS];
		adjMat = new int[MAX_VERTS][MAX_VERTS];
		nVerts = 0;
		for(int i=0;i<MAX_VERTS;i++){
			for(int j=0;j<MAX_VERTS;j++){
				adjMat[i][j] = 0;
			}
		}
		stack = new StackX();
		queue = new Queue();
	}
	
	/**
	 * 添加頂點
	 * @param lab
	 */
	public void addVertex(char lab){
		vertexList[nVerts++] = new Vertex(lab);
	}
	
	/**
	 * 添加邊
	 * @param start
	 * @param end
	 */
	public void addEdge(int start,int end){
		adjMat[start][end] = 1;
		adjMat[end][start] = 1;
	}
	
	/**
	 * 顯示頂點
	 * @param index
	 */
	public void displayVertex(int index){
		System.out.print(vertexList[index].label +" ");
	}
	
	/**
	 * 擷取未通路的相鄰節點
	 * @param index
	 * @return
	 */
	public int getAdjUnvisitedVertex(int index){
		for(int i=0;i<nVerts;i++){
			if(adjMat[index][i]==1&&vertexList[i].visited==false){
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * deep-first search
	 * 規則一、如果可能，通路一個相鄰的未通路的節點，标記它，并放入棧中。
	 * 規則二、當不能執行規則一時，如果棧不為空，那麼從棧中彈出一個頂點。
	 * 規則三、如果不能執行規則一和規則二，就完成了整個搜尋過程。
	 */
	public void dfs(){
		vertexList[0].visited = true;
		displayVertex(0);
		stack.push(0);
		while(!stack.isEmpty()){
			int v = getAdjUnvisitedVertex(stack.peek());
			if(v==-1){
				stack.pop();
			}else{
				vertexList[v].visited = true;
				displayVertex(v);
				stack.push(v);
			}
		}
		
		//stack is empty
		for(int i=0;i<nVerts;i++){
			vertexList[i].visited = false;
		}
		
	}
	
	/**
	 * breadth-first search
	 * 規則一、通路下一個未通路的相鄰節點（如果存在），這個頂點必須是目前頂點的鄰接點，标記它，并把它放入隊列中。
	 * 規則二、如果因為已經沒有未通路的頂點而不能執行規則一，那麼從隊列頭中取出一個頂點（如果存在），并使它成為目前頂點。
	 * 規則三、如果因為隊列為空而不能執行規則二，則搜尋結束。
	 */
	public void bfs(){
		vertexList[0].visited = true;
		displayVertex(0);
		queue.insert(0);
		int v2;
		while(!queue.isEmpty()){
			int v1 = queue.remove();
			while((v2=getAdjUnvisitedVertex(v1))!=-1){
				vertexList[v2].visited = true;
				displayVertex(v2);
				queue.insert(v2);
			}
		}
		
		for(int i=0;i<nVerts;i++){
			vertexList[i].visited = false;
		}
	}
}

    GraphDemo.java

package com.xxx.algorithm.wh.graph;

public class GraphDemo {

	public static void main(String[] args) {
		Graph graph = new Graph();
		graph.addVertex('A');
		graph.addVertex('B');
		graph.addVertex('C');
		graph.addVertex('D');
		graph.addVertex('E');
		
		graph.addEdge(0, 1);
		graph.addEdge(1, 2);
		graph.addEdge(0, 3);
		graph.addEdge(3, 4);
		System.out.print("dfs visits: ");
		graph.dfs();
		System.out.println();
		
		System.out.print("bfs visits: ");
		graph.bfs();
		System.out.println();
	}
	
}

    運作示例程式，控制台列印資訊如下：

dfs visits: A B C D E 
bfs visits: A B D C E

    深度優先搜尋和廣度優先搜尋的結果和我們之前的描述是一直的。

    這裡總結一下圖的資料結構：

  1. 需要使用二維數組即鄰接矩陣來表示圖，還需要使用數組表示頂點。
  2. 深度優先搜尋需要使用到棧，來儲存周遊過的節點，當沒有相鄰節點時需要從棧中彈出節點，當棧為空的時候，周遊結束。
  3. 廣度優先搜尋需要使用到隊列，來儲存周遊過的節點，當沒有相鄰節點的時候從隊頭取出節點，當隊列為空，周遊結束。
java Java圖結構 廣度優先搜尋 深度優先搜尋
上一篇: 關于圖的廣度優先搜尋（BFS）和深度優先搜尋（DFS）
下一篇: JAVA實作圖的深度優先搜尋和廣度優先搜尋 1、深度優先搜尋介紹 2、廣度優先搜尋介紹 3、代碼實作

繼續閱讀