圖的遍歷

• 圖的遍歷是和樹的遍歷類似，我們希望從圖中某一頂點出發(fā)訪遍圖中其余頂點贸街，且使每一個頂點僅被訪問一次沼琉，這一過程就叫做圖的遍歷(Traversing Graph)。
• 重復訪問頂點就不叫做遍歷了奏夫。

• 關(guān)于圖的基本概念怕篷，理論知識不想說了。太繁瑣~
• 直接上圖酗昼，這個應該都能看懂廊谓。

圖的深度優(yōu)先遍歷.png

• 左圖是一個圖，右圖是根據(jù)圖生成的矩陣麻削。

[v0][v1]代表v0頂點到v1頂點的路徑權(quán)重為10
可以看見右圖蒸痹，權(quán)重為0的都是頂點自己到自己，這根本就沒有意義呛哟。
而無限大符號表示到達不了叠荠，比如[v0][v2]∩ㄔ穑可以看左圖榛鼎，v0只能到達v1和v5，到不了v2鳖孤。

第一幅圖的矩陣可以看到有9個頂點者娱，組成二維數(shù)組。

我們可以先生成這個矩陣：

public class Graph {
    
    private int vertexSize; // 頂點數(shù)量
    private int[] vertexs; // 頂點數(shù)組
    private int[][] matrix; // 包含所有頂點的數(shù)組
    // 路徑權(quán)重
    // 0意味著頂點自己到自己苏揣，無意義
    // MAX_WEIGHT也意味著到目的頂點不可達
    private static final int MAX_WEIGHT = 1000;
    
    public Graph(int vertextSize) {
        this.vertexSize = vertextSize;
        matrix = new int[vertextSize][vertextSize];
        vertexs = new int[vertextSize];
        for (int i = 0; i < vertextSize; i++) {
            vertexs[i] = i;
        }
    }
    
    public static void main(String[] args) {
        Graph graph = new Graph(9);

        // 頂點的矩陣設置
        int[] a1 = new int[] { 0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT };
        int[] a2 = new int[] { 10, 0, 18, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, MAX_WEIGHT, 12 };
        int[] a3 = new int[] { MAX_WEIGHT, MAX_WEIGHT, 0, 22, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8 };
        int[] a4 = new int[] { MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, 24, 16, 21 };
        //int[] a4 = new int[] { MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, MAX_WEIGHT, 16, 21 };
        int[] a5 = new int[] { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 20, 0, 26, MAX_WEIGHT, 7, MAX_WEIGHT };
        int[] a6 = new int[] { 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 26, 0, 17, MAX_WEIGHT, MAX_WEIGHT };
        int[] a7 = new int[] { MAX_WEIGHT, 16, MAX_WEIGHT, 24, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT };
        //int[] a7 = new int[] { MAX_WEIGHT, 16, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT };
        int[] a8 = new int[] { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, 7, MAX_WEIGHT, 19, 0, MAX_WEIGHT };
        int[] a9 = new int[] { MAX_WEIGHT, 12, 8, 21, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0 };

        graph.matrix[0] = a1;
        graph.matrix[1] = a2;
        graph.matrix[2] = a3;
        graph.matrix[3] = a4;
        graph.matrix[4] = a5;
        graph.matrix[5] = a6;
        graph.matrix[6] = a7;
        graph.matrix[7] = a8;
        graph.matrix[8] = a9;
    }
}

• 可以看到我們用一個matrix二維數(shù)組存放所有頂點
• 0表示自己到自己黄鳍，MAX_WEIGHT表示無限大
• 然后就是一些實例化和設置矩陣
• 有了這些，我們才能進行遍歷

深度優(yōu)先遍歷

• 深度優(yōu)先遍歷(Depth First Search)腿准，也有稱為深度優(yōu)先搜索际起，簡稱為DFS。

深度優(yōu)先遍歷.png

• 遍歷規(guī)則：不斷的沿著頂點的深度方向遍歷吐葱。頂點的深度方向是指它的鄰接點方向街望。
• 它從圖中某個頂點v出發(fā)，訪問此頂點弟跑，然后從頂點的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖灾前，直至圖中所有和v有路徑相通的頂點都被訪問到。
• 簡單說孟辑，就是頂點將第一個鄰接點當作左孩子哎甲，其它鄰接點都當做右孩子蔫敲。最后排成一棵樹。
• 深度優(yōu)先遍歷是指先遍歷到最深層次炭玫，然后再探索鄰接點奈嘿，接著又遍歷最深層次。二叉樹的先序遍歷就是一種深度優(yōu)先遍歷吞加。

======================================

• 思想與步驟：
• 看上圖右圖裙犹，我們先訪問A，然后訪問A的第一個鄰接點B衔憨。接著訪問B的第一個鄰接點C叶圃。。践图。掺冠。最后訪問到F，F(xiàn)想訪問第一個鄰接點A码党。但是A已經(jīng)訪問過了德崭，只能訪問F的下一個鄰接點G。
• 這就是深度優(yōu)先遍歷的訪問順序闽瓢。
• 在代碼中接癌，依照分析。獲取某頂點的第一個鄰接點和下一個臨界點是經(jīng)常使用的方法扣讼。訪問過程中缺猛，我們要判斷該頂點是否已訪問過，這個也需要輔助變量椭符。

private boolean[] isVisited = new boolean[vertextSize];

/**
 * 獲取指定頂點的第一個鄰接點
 * 
 * @param index
 *          指定鄰接點
 * @return
 */
private int getFirstNeighbor(int index) {
    for (int i = 0; i < vertexSize; i++) {
        if (matrix[index][i] < MAX_WEIGHT && matrix[index][i] > 0) {
            return i;
        }
    }
    return -1;
}

/**
 * 獲取指定頂點的下一個鄰接點
 * 
 * @param v
 *          指定的頂點
 * @param index
 *          從哪個鄰接點開始
 * @return
 */
private int getNextNeighbor(int v, int index) {
    for (int i = index+1; i < vertexSize; i++) {
        if (matrix[v][i] < MAX_WEIGHT && matrix[v][i] > 0) {
            return i;
        }
    }
    return -1;
}

核心代碼很簡單荔燎，經(jīng)上述分析過后：

/**
 * 圖的深度優(yōu)先遍歷算法
 */
private void depthFirstSearch(int i) {
    isVisited[i] = true;
    int w = getFirstNeighbor(i);
    while (w != -1) {
        if (!isVisited[w]) {
            // 需要遍歷該頂點
            System.out.println("訪問到了：" + w + "頂點");
            depthFirstSearch(w); // 進行深度遍歷
        }
        w = getNextNeighbor(i, w); // 第一個相對于w的鄰接點
    }
}

• 傳0進去再层，表示v0绍哎。
• 設置v0已訪問過，獲取v0的第一個鄰接點械念。w != -1說明有這個鄰接點蒸健，然后對這個臨界點進行判斷座享。
  • 已訪問，那就找下一個臨界點
  • 未訪問似忧，進行訪問渣叛，然后對該鄰接點進行深度優(yōu)先遍歷。

• 算法還是很簡單的盯捌！

廣度優(yōu)先遍歷

• 思想(感悟)：
• 廣度優(yōu)先遍歷表示把每一層都遍歷完才能遍歷下一層淳衙。
• 我們來思考：假設v0有3個鄰接點，v1 v2 v3。
  • 我們訪問v0后箫攀，然后訪問v1 v2 v3肠牲。完畢后我們要從v1開始遍歷它的鄰接點，接著從v2開始遍歷它的鄰接點靴跛，最后是從v3開始遍歷它的鄰接點缀雳。
  • 也就是說，3個鄰接點訪問完后汤求。我們要回過頭逐個遍歷它們的鄰接點俏险。這一點我覺得要用個容器把它們順序存儲下來。然后每次從容器首部取出一個頂點開始遍歷扬绪。這里我想到LinkedList，因為它適合增刪裤唠。而且這里不需要遍歷集合挤牛。
• 整體步驟：
  • 我們可以把第一個頂點放進集合，然后while(!queue.isEmpty())或while(queue.size() > 0)都行种蘸。開始循環(huán)墓赴。
  • 然后取出并刪除集合中第一個頂點元素的第一個鄰接點。對這個頂點進行訪問航瞭，
    • 如果該頂點未訪問過诫硕，就訪問！然后將該頂點放入集合刊侯。
    • 如果該頂點已訪問過章办，就找該頂點的下一個鄰接點。

核心代碼：

/**
 * 圖的廣度優(yōu)先遍歷算法
 */
private void boardFirstSearch(int i) {
    LinkedList<Integer> queue = new LinkedList<>(); 
    System.out.println("訪問到了：" + i + "頂點");
    isVisited[i] = true;
    queue.add(i);
    
    while (queue.size() > 0) {
        int w = queue.removeFirst().intValue();
        int n = getFirstNeighbor(w);
        while (n != -1) {
            if (!isVisited[n]) {
                System.out.println("訪問到了：" + n + "頂點");
                isVisited[n] = true;
                queue.add(n);
            }
            n = getNextNeighbor(w, n);
        }
    }
}

完整代碼

復制即可運行

import java.util.LinkedList;

public class Graph {
    
    private int vertexSize; // 頂點數(shù)量
    private int[] vertexs; // 頂點數(shù)組
    private int[][] matrix; // 包含所有頂點的數(shù)組
    // 路徑權(quán)重
    // 0意味著頂點自己到自己滨彻，無意義
    // MAX_WEIGHT也意味著到目的頂點不可達
    private static final int MAX_WEIGHT = 1000;
    private boolean[] isVisited; // 某頂點是否被訪問過
    
    public Graph(int vertextSize) {
        this.vertexSize = vertextSize;
        matrix = new int[vertextSize][vertextSize];
        vertexs = new int[vertextSize];
        for (int i = 0; i < vertextSize; i++) {
            vertexs[i] = i;
        }
        isVisited = new boolean[vertextSize];
    }
    
    /**
     * 獲取指定頂點的第一個鄰接點
     * 
     * @param index
     *          指定鄰接點
     * @return
     */
    private int getFirstNeighbor(int index) {
        for (int i = 0; i < vertexSize; i++) {
            if (matrix[index][i] < MAX_WEIGHT && matrix[index][i] > 0) {
                return i;
            }
        }
        return -1;
    }
    
    /**
     * 獲取指定頂點的下一個鄰接點
     * 
     * @param v
     *          指定的頂點
     * @param index
     *          從哪個鄰接點開始
     * @return
     */
    private int getNextNeighbor(int v, int index) {
        for (int i = index+1; i < vertexSize; i++) {
            if (matrix[v][i] < MAX_WEIGHT && matrix[v][i] > 0) {
                return i;
            }
        }
        return -1;
    }
    
    /**
     * 圖的深度優(yōu)先遍歷算法
     */
    private void depthFirstSearch(int i) {
        isVisited[i] = true;
        int w = getFirstNeighbor(i);
        while (w != -1) {
            if (!isVisited[w]) {
                // 需要遍歷該頂點
                System.out.println("訪問到了：" + w + "頂點");
                depthFirstSearch(w); // 進行深度遍歷
            }
            w = getNextNeighbor(i, w); // 第一個相對于w的鄰接點
        }
    }
    
    /**
     * 圖的廣度優(yōu)先遍歷算法
     */
    private void boardFirstSearch(int i) {
        LinkedList<Integer> queue = new LinkedList<>(); 
        System.out.println("訪問到了：" + i + "頂點");
        isVisited[i] = true;
        queue.add(i);
        
        while (queue.size() > 0) {
            int w = queue.removeFirst().intValue();
            int n = getFirstNeighbor(w);
            while (n != -1) {
                if (!isVisited[n]) {
                    System.out.println("訪問到了：" + n + "頂點");
                    isVisited[n] = true;
                    queue.add(n);
                }
                n = getNextNeighbor(w, n);
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(9);

        // 頂點的矩陣設置
        int[] a1 = new int[] { 0, 10, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT };
        int[] a2 = new int[] { 10, 0, 18, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, MAX_WEIGHT, 12 };
        int[] a3 = new int[] { MAX_WEIGHT, MAX_WEIGHT, 0, 22, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 8 };
        int[] a4 = new int[] { MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, 24, 16, 21 };
        //int[] a4 = new int[] { MAX_WEIGHT, MAX_WEIGHT, 22, 0, 20, MAX_WEIGHT, MAX_WEIGHT, 16, 21 };
        int[] a5 = new int[] { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 20, 0, 26, MAX_WEIGHT, 7, MAX_WEIGHT };
        int[] a6 = new int[] { 11, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 26, 0, 17, MAX_WEIGHT, MAX_WEIGHT };
        int[] a7 = new int[] { MAX_WEIGHT, 16, MAX_WEIGHT, 24, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT };
        //int[] a7 = new int[] { MAX_WEIGHT, 16, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 17, 0, 19, MAX_WEIGHT };
        int[] a8 = new int[] { MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 16, 7, MAX_WEIGHT, 19, 0, MAX_WEIGHT };
        int[] a9 = new int[] { MAX_WEIGHT, 12, 8, 21, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, MAX_WEIGHT, 0 };

        graph.matrix[0] = a1;
        graph.matrix[1] = a2;
        graph.matrix[2] = a3;
        graph.matrix[3] = a4;
        graph.matrix[4] = a5;
        graph.matrix[5] = a6; 
        graph.matrix[6] = a7;
        graph.matrix[7] = a8;
        graph.matrix[8] = a9;
        
        graph.depthFirstSearch(0);
        //graph.boardFirstSearch(0);
    }

}