/**
 * 頂點(diǎn)類
 * @author vae
 */
public class Vertex {
    public char label;
    public boolean wasVisited;
    public Vertex(char label){
        this.label = label;
        wasVisited = false;
    }
}

package com.ys.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 j){
        st[++top] = j;
    }
    public int pop(){
        return st[top--];
    }
    public int peek(){
        return st[top];
    }
    public boolean isEmpty(){
        return (top == -1);
    }
}

package com.ys.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 j) {
        if(rear == SIZE-1) {
            rear = -1;
        }
        queArray[++rear] = j;
    }
    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);
    }
}

package com.ys.graph;
public class Graph {
    private final int MAX_VERTS = 20;//表示頂點(diǎn)的個數(shù)
    private Vertex vertexList[];//用來存儲頂點(diǎn)的數(shù)組
    private int adjMat[][];//用鄰接矩陣來存儲 邊,數(shù)組元素0表示沒有邊界，1表示有邊界
    private int nVerts;//頂點(diǎn)個數(shù)
    private StackX theStack;//用棧實(shí)現(xiàn)深度優(yōu)先搜索
    private Queue queue;//用隊(duì)列實(shí)現(xiàn)廣度優(yōu)先搜索
    /**
     * 頂點(diǎn)類
     * @author vae
     */
    class Vertex {
        public char label;
        public boolean wasVisited;
        public Vertex(char label){
            this.label = label;
            wasVisited = false;
        }
    }
    public Graph(){
        vertexList = new Vertex[MAX_VERTS];
        adjMat = new int[MAX_VERTS][MAX_VERTS];
        nVerts = 0;//初始化頂點(diǎn)個數(shù)為0
        //初始化鄰接矩陣所有元素都為0，即所有頂點(diǎn)都沒有邊
        for(int i = 0; i < MAX_VERTS; i++) {
            for(int j = 0; j < MAX_VERTS; j++) {
                adjMat[i][j] = 0;
            }
        }
        theStack = new StackX();
        queue = new Queue();
    }
    //將頂點(diǎn)添加到數(shù)組中，是否訪問標(biāo)志置為wasVisited=false(未訪問)
    public void addVertex(char lab) {
        vertexList[nVerts++] = new Vertex(lab);
    }
    //注意用鄰接矩陣表示邊，是對稱的，兩部分都要賦值
    public void addEdge(int start, int end) {
        adjMat[start][end] = 1;
        adjMat[end][start] = 1;
    }
    //打印某個頂點(diǎn)表示的值
    public void displayVertex(int v) {
        System.out.print(vertexList[v].label);
    }
    /**深度優(yōu)先搜索算法:
     * 1、用peek()方法檢查棧頂?shù)捻旤c(diǎn)
     * 2、用getAdjUnvisitedVertex()方法找到當(dāng)前棧頂點(diǎn)鄰接且未被訪問的頂點(diǎn)
     * 3、第二步方法返回值不等于-1則找到下一個未訪問的鄰接頂點(diǎn)，訪問這個頂點(diǎn)，并入棧
     *    如果第二步方法返回值等于 -1，則沒有找到，出棧
     */
    public void depthFirstSearch() {
        //從第一個頂點(diǎn)開始訪問
        vertexList[0].wasVisited = true; //訪問之后標(biāo)記為true
        displayVertex(0);//打印訪問的第一個頂點(diǎn)
        theStack.push(0);//將第一個頂點(diǎn)放入棧中
        while(!theStack.isEmpty()) {
            //找到棧當(dāng)前頂點(diǎn)鄰接且未被訪問的頂點(diǎn)
            int v = getAdjUnvisitedVertex(theStack.peek());
            if(v == -1) {   //如果當(dāng)前頂點(diǎn)值為-1，則表示沒有鄰接且未被訪問頂點(diǎn)，那么出棧頂點(diǎn)
                theStack.pop();
            }else { //否則訪問下一個鄰接頂點(diǎn)
                vertexList[v].wasVisited = true;
                displayVertex(v);
                theStack.push(v);
            }
        }
        //棧訪問完畢，重置所有標(biāo)記位wasVisited=false
        for(int i = 0; i < nVerts; i++) {
            vertexList[i].wasVisited = false;
        }
    }
    //找到與某一頂點(diǎn)鄰接且未被訪問的頂點(diǎn)
    public int getAdjUnvisitedVertex(int v) {
        for(int i = 0; i < nVerts; i++) {
            //v頂點(diǎn)與i頂點(diǎn)相鄰（鄰接矩陣值為1）且未被訪問 wasVisited==false
            if(adjMat[v][i] == 1 && vertexList[i].wasVisited == false) {
                return i;
            }
        }
        return -1;
    }
    /**
     * 廣度優(yōu)先搜索算法：
     * 1、用remove()方法檢查棧頂?shù)捻旤c(diǎn)
     * 2、試圖找到這個頂點(diǎn)還未訪問的鄰節(jié)點(diǎn)
     * 3、 如果沒有找到，該頂點(diǎn)出列
     * 4、 如果找到這樣的頂點(diǎn)，訪問這個頂點(diǎn)，并把它放入隊(duì)列中
     */
    public void breadthFirstSearch(){
        vertexList[0].wasVisited = true;
        displayVertex(0);
        queue.insert(0);
        int v2;
        while(!queue.isEmpty()) {
            int v1 = queue.remove();
            while((v2 = getAdjUnvisitedVertex(v1)) != -1) {
                vertexList[v2].wasVisited = true;
                displayVertex(v2);
                queue.insert(v2);
            }
        }
        //搜索完畢，初始化，以便于下次搜索
        for(int i = 0; i < nVerts; i++) {
            vertexList[i].wasVisited = false;
        }
    }
    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);//AB
        graph.addEdge(1, 2);//BC
        graph.addEdge(0, 3);//AD
        graph.addEdge(3, 4);//DE
        System.out.println("深度優(yōu)先搜索算法 :");
        graph.depthFirstSearch();//ABCDE
        System.out.println();
        System.out.println("----------------------");
        System.out.println("廣度優(yōu)先搜索算法 :");
        graph.breadthFirstSearch();//ABDCE
    }
}

//基于深度優(yōu)先搜索找到最小生成樹
public void mst(){
    vertexList[0].wasVisited = true;
    theStack.push(0);
    while(!theStack.isEmpty()){
        int currentVertex = theStack.peek();
        int v = getAdjUnvisitedVertex(currentVertex);
        if(v == -1){
            theStack.pop();
        }else{
            vertexList[v].wasVisited = true;
            theStack.push(v);
            displayVertex(currentVertex);
            displayVertex(v);
            System.out.print(" ");
        }
    }
    //搜索完畢，初始化，以便于下次搜索
    for(int i = 0; i < nVerts; i++) {
        vertexList[i].wasVisited = false;
    }
}