JAVA實作圖的深度優先搜尋和廣度優先搜尋

1、深度優先搜尋介紹

圖的深度優先搜尋(Depth First Search)，和樹的先序周遊比較類似。

它的思想：假設初始狀态是圖中所有頂點均未被通路，則從某個頂點v出發，首先通路該頂點，然後依次從它的各個未被通路的鄰接點出發深度優先搜尋周遊圖，直至圖中所有和v有路徑相通的頂點都被通路到。 若此時尚有其他頂點未被通路到，則另選一個未被通路的頂點作起始點，重複上述過程，直至圖中所有頂點都被通路到為止。

顯然，深度優先搜尋是一個遞歸的過程。

2、廣度優先搜尋介紹

廣度優先搜尋算法(Breadth First Search)，又稱為"寬度優先搜尋"或"橫向優先搜尋"，簡稱BFS。

它的思想是：從圖中某頂點v出發，在通路了v之後依次通路v的各個未曾通路過的鄰接點，然後分别從這些鄰接點出發依次通路它們的鄰接點，并使得“先被通路的頂點的鄰接點先于後被通路的頂點的鄰接點被通路，直至圖中所有已被通路的頂點的鄰接點都被通路到。如果此時圖中尚有頂點未被通路，則需要另選一個未曾被通路過的頂點作為新的起始點，重複上述過程，直至圖中所有頂點都被通路到為止。

換句話說，廣度優先搜尋周遊圖的過程是以v為起點，由近至遠，依次通路和v有路徑相通且路徑長度為1,2...的頂點。

3、代碼實作

深度優先搜尋需要用到Stack

廣度優先搜尋需要用到Queue

頂點類：

public class Vertex {

    public char label;

    // 辨別是否已經被通路過了
    public boolean isVisit;

    public Vertex(char label, boolean isVisit) {
        this.label = label;
        this.isVisit = isVisit;
    }
}
           

圖類：

public class Graph {

    // 頂點的數組
    private Vertex[] vertexList;

    // 鄰接矩陣
    private int[][] adjMat;

    // 數組最大大小
    private int maxSize;

    // 目前數組大小
    private int nVertex;

    /**
     * 初始化頂點數組、鄰接矩陣
     */
    public Graph(int maxSize) {
        this.maxSize = maxSize;
        vertexList = new Vertex[maxSize];
        adjMat = new int[maxSize][maxSize];
        for (int i = 0; i < maxSize; i++) {
            for (int j = 0; j < maxSize; j++) {
                adjMat[i][j] = 0;
            }
        }
        nVertex = 0;
    }

    /**
     * 添加頂點
     */
    public void addVertex(char label) {
        vertexList[nVertex++] = new Vertex(label, false);
    }

    /**
     * 添加邊
     */
    public void addEdge(int start, int end) {
        adjMat[start][end] = 1;
        adjMat[end][start] = 1;
    }

    /**
     * 深度優先搜尋
     */
    public void dfs() {

        // 從0号頂點開始
        int v = 0;
        String result = vertexList[v].label + " ";
        vertexList[v].isVisit = true;

        MyStack stack = new MyStack();
        stack.push(v);

        while (!stack.isEmpty()) {
            v = stack.peek();
            // 得到未通路過的鄰接點
            int unvisitedVertex = getUnvisitedVertex(v);
            if(unvisitedVertex == -1) {
                stack.pop();
            } else{
                result += vertexList[unvisitedVertex].label + " ";
                vertexList[unvisitedVertex].isVisit = true;
                stack.push(unvisitedVertex);
            }
        }

        System.out.println(result);

        // 将通路資訊重置
        resetVisit();
    }

    /**
     * 廣度優先搜尋
     */
    public void bfs() {

        // 從0号頂點開始
        int v = 0;
        vertexList[v].isVisit = true;
        String result = vertexList[v].label + " ";

        MyQueue queue = new MyQueue(100);
        queue.insert(v);

        while (!queue.isEmpty()) {
            v = queue.peek();
            // 得到未通路過的鄰接點
            int unvisitedVertex = getUnvisitedVertex(v);
            if(unvisitedVertex == -1) {
                queue.remove();
            } else {
                vertexList[unvisitedVertex].isVisit = true;
                result += vertexList[unvisitedVertex].label + " ";
                queue.insert(unvisitedVertex);
            }
        }
        System.out.println(result);

        // 将通路資訊重置
        resetVisit();
    }

    /**
     * 擷取未通路過的鄰接點
     */
    public int getUnvisitedVertex(int v) {

        for (int i = 0; i < nVertex; i++) {
            if(adjMat[v][i] == 1 && vertexList[i].isVisit == false) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 将通路資訊的屬性重置
     */
    private void resetVisit() {
        for (int i = 0; i < vertexList.length; i++) {
            vertexList[i].isVisit = false;
        }
    }

    /**
     * 列印圖矩陣
     */
    public void printGraph() {
        System.out.println("********************************************");
        System.out.print("\\ \t");
        for (int i = 0; i < maxSize; i++) {
            System.out.print(vertexList[i].label + "\t");
        }
        System.out.println();
        for (int i = 0; i < maxSize; i++) {
            System.out.print(vertexList[i].label + "\t");
            for (int j = 0; j < maxSize; j++) {
                System.out.print(adjMat[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println("********************************************");
    }

}
           

測試類：

public class Test {

    public static void main(String[] args) {

        Graph graph = new Graph(10);

        graph.addVertex('A');
        graph.addVertex('B');
        graph.addVertex('C');
        graph.addVertex('D');
        graph.addVertex('E');
        graph.addVertex('F');
        graph.addVertex('G');
        graph.addVertex('H');
        graph.addVertex('I');
        graph.addVertex('J');

        graph.addEdge(0,1);
        graph.addEdge(1,2);
        graph.addEdge(2,3);
        graph.addEdge(0,4);
        graph.addEdge(4,5);
        graph.addEdge(5,6);
        graph.addEdge(0,7);
        graph.addEdge(7,8);
        graph.addEdge(8,9);

        graph.printGraph();

        graph.dfs();

        graph.bfs();
    }
}
           

Stack類：

public class MyStack {

	//底層實作是一個數組
	private int[] arr;
	private int top;
	
	/**
	 * 預設的構造方法
	 */
	public MyStack() {
		arr = new int[10];
		top = -1;
	}
	
	/**
	 * 帶參數構造方法，參數為數組初始化大小
	 */
	public MyStack(int maxsize) {
		arr = new int[maxsize];
		top = -1;
	}
	
	/**
	 * 添加資料
	 */
	public void push(int value) {
		arr[++top] = value;
	}
	
	/**
	 * 移除資料
	 */
	public int pop() {
		return arr[top--];
	}
	
	/**
	 * 檢視資料
	 */
	public int peek() {
		return arr[top];
	}
	
	/**
	 * 判斷是否為空
	 */
	public boolean isEmpty() {
		return top == -1;
	}
	
	/**
	 * 判斷是否滿了
	 */
	public boolean isFull() {
		return top == arr.length - 1;
	}
}
           

Queue類：

public class MyQueue {
	//底層使用數組
	private int[] arr;
	//有效資料的大小
	private int elements;
	//隊頭
	private int front;
	//隊尾
	private int end;
	
	/**
	 * 預設構造方法
	 */
	public MyQueue() {
		arr = new int[10];
		elements = 0;
		front = 0;
		end = -1;
	}
	
	/**
	 * 帶參數的構造方法，參數為數組的大小
	 */
	public MyQueue(int maxsize) {
		arr = new int[maxsize];
		elements = 0;
		front = 0;
		end = -1;
	}
	
	/**
	 * 添加資料,從隊尾插入
	 */
	public void insert(int value) {
		arr[++end] = value;
		elements++;
	}
	
	/**
	 * 删除資料，從隊頭删除
	 */
	public int remove() {
		elements--;
		return arr[front++];
	}
	
	/**
	 * 檢視資料，從隊頭檢視
	 */
	public int peek() {
		return arr[front];
	}
	
	/**
	 * 判斷是否為空
	 */
	public boolean isEmpty() {
		return elements == 0;
	}
	
	/**
	 * 判斷是否滿了
	 */
	public boolean isFull() {
		return elements == arr.length;
	}
}