在講深度優(yōu)先遍歷之前，先來(lái)回顧一下圖這種數(shù)據(jù)結(jié)構(gòu)。

1. 是什么？

圖，也是一種數(shù)據(jù)結(jié)構(gòu)，其節(jié)點(diǎn)可以具有零個(gè)或者多個(gè)相鄰元素，兩個(gè)節(jié)點(diǎn)之間的連接稱(chēng)為邊，節(jié)點(diǎn)也稱(chēng)為頂點(diǎn)，圖表示的是多對(duì)多的關(guān)系。

2. 圖的常用概念：

• 頂點(diǎn)：就是節(jié)點(diǎn)，上圖中的ABCDEFGH都是頂點(diǎn)；

• 邊：每個(gè)節(jié)點(diǎn)之間的連線(xiàn)叫做邊；

• 路徑：從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的通路，比如從A到G的路徑有：A ---> B ---> G和A ---> F ---> G；

• 無(wú)向圖：上面的就是無(wú)向圖，就是節(jié)點(diǎn)之間的連線(xiàn)是沒(méi)有方向的，A可以到B，B也可以到A；

• 有向圖：節(jié)點(diǎn)之間的連線(xiàn)是有方向的；

• 帶權(quán)圖：邊具有權(quán)值的圖叫做帶權(quán)圖，也叫網(wǎng)。

3. 圖的表示方式：

• 鄰接矩陣：也就是用二維數(shù)組表示。假如總共有n個(gè)頂點(diǎn)，那么就需要一個(gè) n*n 的二維數(shù)組。兩個(gè)頂點(diǎn)之間如果是連通的就用1表示，反之用0表示。這種方式的缺點(diǎn)就是，假如n很大，但是相互連通的頂點(diǎn)卻很少，即一個(gè)二維數(shù)組中真正有用的數(shù)據(jù)特別少，那么就會(huì)造成空間的浪費(fèi)；

• 鄰接表：鄰接表只關(guān)心存在的邊，即只關(guān)注能相互連通的頂點(diǎn)，因此沒(méi)有空間浪費(fèi)。鄰接表用數(shù)組和鏈表組合實(shí)現(xiàn)。數(shù)組下標(biāo)表示頂點(diǎn)編號(hào)，數(shù)組中存的值是一條鏈表，鏈表中的數(shù)據(jù)就是數(shù)組該下標(biāo)對(duì)應(yīng)頂點(diǎn)連通的頂點(diǎn)編號(hào)。比如頂點(diǎn)0可以和頂點(diǎn)2，3，6連通，那么數(shù)組第一個(gè)位置存放的就是2 ---> 3 ---> 6這條鏈表。

4. 無(wú)向圖的創(chuàng)建(鄰接矩陣)：

開(kāi)篇所示的無(wú)向圖，怎么用鄰接矩陣代碼實(shí)現(xiàn)呢？思路如下：

• 創(chuàng)建一個(gè)List<String>，用來(lái)保存各個(gè)頂點(diǎn)；

• 創(chuàng)建一個(gè)二維數(shù)組，用來(lái)保存頂點(diǎn)之間的邊，頂點(diǎn)與頂點(diǎn)之間有連線(xiàn)的用1表示，反之用0。所以這個(gè)二位數(shù)組就是：

  A  B  C  D  E  F  G  H
A[0, 1, 0, 0, 0, 1, 0, 1]
B[1, 0, 1, 0, 0, 0, 1, 0]
C[0, 1, 0, 1, 1, 0, 0, 0]
D[0, 0, 1, 0, 0, 0, 0, 1]
E[0, 0, 1, 0, 0, 0, 1, 0]
F[1, 0, 0, 0, 0, 0, 1, 0]
G[0, 1, 0, 0, 1, 1, 0, 0]
H[1, 0, 0, 1, 0, 0, 0, 0]

• 所以，創(chuàng)建圖也就是創(chuàng)建這個(gè)鄰接矩陣，代碼如下：

public class UnDirectionGraph {

    private List<String> vertexList; // 存放頂點(diǎn)
    private int[][] edges; // 鄰接矩陣，存放圖的邊
    private boolean[] isVisited; // 頂點(diǎn)是否被訪(fǎng)問(wèn)

    /**
     * 構(gòu)造器
     * @param vertexCount 頂點(diǎn)的個(gè)數(shù)
     */
    public UnDirectionGraph(int vertexCount, List<String> vertex){
        this.vertexList = vertex;
        this.edges = new int[vertexCount][vertexCount];
        this.isVisited = new boolean[vertexCount];
    }

    /**
     * 構(gòu)建無(wú)向圖
     * @param vertex1 頂點(diǎn)1
     * @param vertex2 頂點(diǎn)2
     * @param isConnected 頂點(diǎn)1和頂點(diǎn)2是否連通，0:未連通 1:已連通
     */
    public void buildGraph(String vertex1, String vertex2, int isConnected){
        edges[vertexList.indexOf(vertex1)][vertexList.indexOf(vertex2)] = isConnected;
        edges[vertexList.indexOf(vertex2)][vertexList.indexOf(vertex1)] = isConnected;
    }

   /**
     * 打印鄰接矩陣
     */
    public void printGraph(){
        for(int[] arr : edges){
            System.out.println(Arrays.toString(arr));
        }
    }
}

測(cè)試代碼：

public static void main(String[] args) {
        int vertexCount = 8;
        List<String> vertexList = new ArrayList<>();
        vertexList.add("A");
        vertexList.add("B");
        vertexList.add("C");
        vertexList.add("D");
        vertexList.add("E");
        vertexList.add("F");
        vertexList.add("G");
        vertexList.add("H");

        UnDirectionGraph graph = new UnDirectionGraph(vertexCount, vertexList);
        graph.buildGraph("A", "B", 1);
        graph.buildGraph("A", "H", 1);
        graph.buildGraph("A", "F", 1);
        graph.buildGraph("B", "G", 1);
        graph.buildGraph("B", "C", 1);
        graph.buildGraph("C", "D", 1);
        graph.buildGraph("C", "E", 1);
        graph.buildGraph("D", "H", 1);
        graph.buildGraph("E", "G", 1);
        graph.buildGraph("F", "G", 1);
        graph.printGraph();
    }

5. 無(wú)向圖的遍歷：

(1). 遍歷分類(lèi)：

圖的遍歷分為兩種：

• 深度優(yōu)先：depth first search，簡(jiǎn)稱(chēng)DFS。先從初始頂點(diǎn)出發(fā)，訪(fǎng)問(wèn)第一個(gè)鄰接頂點(diǎn)，然后再以這個(gè)被訪(fǎng)問(wèn)到的鄰接頂點(diǎn)作為初始頂點(diǎn)，訪(fǎng)問(wèn)它的第一個(gè)鄰接頂點(diǎn)?？梢岳斫鉃橐粭l路走到底，而不是把一個(gè)頂點(diǎn)的所有鄰接頂點(diǎn)先進(jìn)行橫向訪(fǎng)問(wèn)，而是縱向優(yōu)先，所以也叫深度優(yōu)先。

• 廣度優(yōu)先：broad first search，簡(jiǎn)稱(chēng)BFS。類(lèi)似于二叉樹(shù)的層序遍歷，具體的本文不做介紹。

(2). 深度優(yōu)先算法步驟：

以開(kāi)篇中的圖為例：

• 訪(fǎng)問(wèn)A，并將A標(biāo)記為已訪(fǎng)問(wèn)；

• 找到A的第一個(gè)未被訪(fǎng)問(wèn)鄰接頂點(diǎn)，怎么找？看矩陣：

  A  B  C  D  E  F  G  H
A[0, 1, 0, 0, 0, 1, 0, 1]

第一個(gè)1對(duì)應(yīng)的是B，所以A的第一個(gè)鄰接頂點(diǎn)是B，所以第二個(gè)遍歷出來(lái)的是B，并且標(biāo)記B為已訪(fǎng)問(wèn)；

• 找到B的第一個(gè)未被訪(fǎng)問(wèn)的鄰接頂點(diǎn)，方式一樣，看矩陣：

  A  B  C  D  E  F  G  H
B[1, 0, 1, 0, 0, 0, 1, 0]

找到的是C，所以第三個(gè)遍歷出來(lái)的是C，并且標(biāo)記C為已訪(fǎng)問(wèn)；

• 找到C的第一個(gè)未被訪(fǎng)問(wèn)的鄰接頂點(diǎn)，是D，打印D，并標(biāo)記為已訪(fǎng)問(wèn)；

• 找到D的第一個(gè)未被訪(fǎng)問(wèn)的鄰接頂點(diǎn)，是H，打印H，并標(biāo)記為已訪(fǎng)問(wèn)；

• 找到H的第一個(gè)未被訪(fǎng)問(wèn)的鄰接頂點(diǎn)，發(fā)現(xiàn)沒(méi)有，也就是這條路走到底了，那么開(kāi)始往回走；

• 回到D，沒(méi)有未被訪(fǎng)問(wèn)的，再往回，直到回到C；

• 回到C，找到C的第一個(gè)鄰接頂點(diǎn)D的后一個(gè)鄰接頂點(diǎn)：

  A  B  C  D  E  F  G  H
C[0, 1, 0, 1, 1, 0, 0, 0]

說(shuō)白了就是這一行的D后面的那個(gè)1，就是E，打印E，并標(biāo)記為已訪(fǎng)問(wèn)；

• 找到E的第一個(gè)未被訪(fǎng)問(wèn)的鄰接頂點(diǎn)G，打印G；

• 找到G的第一個(gè)未被訪(fǎng)問(wèn)的鄰接頂點(diǎn)F，打印F；

• 到了F，發(fā)現(xiàn)F的所有鄰接頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)了，往回走，發(fā)現(xiàn)所有頂點(diǎn)的鄰接頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)了，就遍歷完了，所以遍歷的結(jié)果就是：

A --- B --- C --- D --- H --- E --- G --- F

其實(shí)概括地說(shuō)就是：從第一個(gè)頂點(diǎn)開(kāi)始，每次都選擇該頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)往下走，走到死胡同的時(shí)候，就往回走，回到最后一次有岔路的地方，換另一條岔路走，又走到死胡同繼續(xù)往回走……

(3). 深度優(yōu)先遍歷代碼：

首先得在UnDirectionGraph類(lèi)中加一個(gè)變量，用來(lái)表示該頂點(diǎn)有沒(méi)有被訪(fǎng)問(wèn)過(guò)，如下：

private boolean[] isVisited; // 頂點(diǎn)是否被訪(fǎng)問(wèn)

然后在UnDirectionGraph中再增加如下方法：

   /**
     * 查找頂點(diǎn)vertex的第一個(gè)鄰接頂點(diǎn)
     * @param vertex
     */
    public int findFstNeighbor(String vertex){
        // 拿到vertex的索引
        int vertexIndex = vertexList.indexOf(vertex);
        // 遍歷二維數(shù)組的第 vertexIndex 行
        int[] arr = edges[vertexIndex];
        for (int i = 0; i < arr.length; i++) {
            // 如果arr[i] = 1，說(shuō)明i對(duì)應(yīng)的頂點(diǎn)就是vertex的鄰接頂點(diǎn)
            if (arr[i] == 1){
                return i;
            }
        }
        return -1;
    }

    /**
     * 根據(jù)vertex的前一個(gè)鄰接頂點(diǎn)priorVertexIndex，找到下一個(gè)鄰接頂點(diǎn)
     * @param vertex
     * @param priorVertexIndex
     * @return
     */
    public int findNeighborByPriorNeighbor(String vertex, int priorVertexIndex){
        // 拿到vertex的索引
        int vertexIndex = vertexList.indexOf(vertex);
        // 從(priorVertexIndex + 1)開(kāi)始遍歷二維數(shù)組的第 vertexIndex 行
        int[] arr = edges[vertexIndex];
        for (int i = priorVertexIndex + 1; i < arr.length; i++) {
            if (arr[i] == 1){
                return i;
            }
        }
        return -1;
    }

    /**
     * 深度優(yōu)先遍歷
     * @param vertex
     */
    private void dfs(String vertex, boolean[] isVisited){
        // 打印當(dāng)前頂點(diǎn)
        System.out.print(vertex + " --- ");
        // 標(biāo)記當(dāng)前頂點(diǎn)已經(jīng)訪(fǎng)問(wèn)
        isVisited[vertexList.indexOf(vertex)] = true;
        // 找到當(dāng)前頂點(diǎn)第一個(gè)鄰接頂點(diǎn)
        int neighbor = findFstNeighbor(vertex);
        // 不等于-1，就打印，并且把第一個(gè)鄰接頂點(diǎn)當(dāng)成當(dāng)前頂點(diǎn)，再去找它的第一個(gè)鄰接頂點(diǎn)
        while (neighbor != -1){
            // 如果neighbor沒(méi)有被訪(fǎng)問(wèn)過(guò)
            if (!isVisited[neighbor]){
                dfs(vertexList.get(neighbor), isVisited);
            } else {
                // 如果neighbor被訪(fǎng)問(wèn)過(guò)了，就找下一個(gè)鄰接頂點(diǎn)
                neighbor = findNeighborByPriorNeighbor(vertex, neighbor);
            }
        }
        // 跳出循環(huán)，說(shuō)明一條路走到底了，就應(yīng)該開(kāi)始回溯，怎么回溯？
        // 其實(shí)外面再寫(xiě)個(gè)方法，循環(huán)vertexList，讓每個(gè)未被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)都調(diào)用這個(gè)方法就好了
    }

    public void dfs() {
        for (String str : vertexList){
            if (!isVisited[vertexList.indexOf(str)]){
                dfs(str, isVisited);
            }
        }
    }

深度優(yōu)先遍歷的方法都寫(xiě)了詳細(xì)注釋?zhuān)@里不再贅述。說(shuō)一說(shuō)找某個(gè)頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)(findFstNeighbor)和找某個(gè)頂點(diǎn)指定鄰接頂點(diǎn)后面的那個(gè)鄰接頂點(diǎn)(findNeighborByPriorNeighbor)這兩個(gè)方法。

• findFstNeighbor：我們構(gòu)建好了二維數(shù)組，即鄰接矩陣，所以找某個(gè)頂點(diǎn)的鄰接頂點(diǎn)直接在矩陣中找就可以。比如我要找A的第一個(gè)鄰接頂點(diǎn)，那就遍歷A所在的那一行，找到第一個(gè)1出現(xiàn)位置的索引，該索引對(duì)應(yīng)的就是A的第一個(gè)鄰接頂點(diǎn)。如下：

  A  B  C  D  E  F  G  H
A[0, 1, 0, 0, 0, 1, 0, 1]

A對(duì)應(yīng)的就是這一行，第一個(gè)1出現(xiàn)的位置的索引是1，1在vertexList中對(duì)應(yīng)的是B，所以A的第一個(gè)鄰接頂點(diǎn)就是B。

• findNeighborByPriorNeighbor：這個(gè)方法是什么意思呢？比如我傳入的參數(shù)是A，1，意思就是我要找A的鄰接頂點(diǎn)，找什么要的鄰接頂點(diǎn)？就是在

  A  B  C  D  E  F  G  H
A[0, 1, 0, 0, 0, 1, 0, 1]

這一行中，找到位置1后面的那個(gè)鄰接頂點(diǎn)，即找到位置1后面的1第一次出現(xiàn)的位置的索引，顯然對(duì)應(yīng)的索引是5，在vertexList中對(duì)應(yīng)的是F。