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

1. 是什么？

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

2. 圖的常用概念：

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

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

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

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

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

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

3. 圖的表示方式：

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

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

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

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

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

• 創(chuàng)建一個二維數(shù)組，用來保存頂點(diǎn)之間的邊，頂點(diǎn)與頂點(diǎn)之間有連線的用1表示，反之用0。所以這個二位數(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)建這個鄰接矩陣，代碼如下：

public class UnDirectionGraph {

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

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

    /**
     * 構(gòu)建無向圖
     * @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));
        }
    }
}

測試代碼：

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. 無向圖的遍歷：

(1). 遍歷分類：

圖的遍歷分為兩種：

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

• 廣度優(yōu)先：broad first search，簡稱BFS。類似于二叉樹的層序遍歷，具體的本文不做介紹。

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

以開篇中的圖為例：

• 訪問A，并將A標(biāo)記為已訪問；

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

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

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

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

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

找到的是C，所以第三個遍歷出來的是C，并且標(biāo)記C為已訪問；

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

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

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

• 回到D，沒有未被訪問的，再往回，直到回到C；

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

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

說白了就是這一行的D后面的那個1，就是E，打印E，并標(biāo)記為已訪問；

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

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

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

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

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

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

首先得在UnDirectionGraph類中加一個變量，用來表示該頂點(diǎn)有沒有被訪問過，如下：

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

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

   /**
     * 查找頂點(diǎn)vertex的第一個鄰接頂點(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，說明i對應(yīng)的頂點(diǎn)就是vertex的鄰接頂點(diǎn)
            if (arr[i] == 1){
                return i;
            }
        }
        return -1;
    }

    /**
     * 根據(jù)vertex的前一個鄰接頂點(diǎn)priorVertexIndex，找到下一個鄰接頂點(diǎn)
     * @param vertex
     * @param priorVertexIndex
     * @return
     */
    public int findNeighborByPriorNeighbor(String vertex, int priorVertexIndex){
        // 拿到vertex的索引
        int vertexIndex = vertexList.indexOf(vertex);
        // 從(priorVertexIndex + 1)開始遍歷二維數(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)訪問
        isVisited[vertexList.indexOf(vertex)] = true;
        // 找到當(dāng)前頂點(diǎn)第一個鄰接頂點(diǎn)
        int neighbor = findFstNeighbor(vertex);
        // 不等于-1，就打印，并且把第一個鄰接頂點(diǎn)當(dāng)成當(dāng)前頂點(diǎn)，再去找它的第一個鄰接頂點(diǎn)
        while (neighbor != -1){
            // 如果neighbor沒有被訪問過
            if (!isVisited[neighbor]){
                dfs(vertexList.get(neighbor), isVisited);
            } else {
                // 如果neighbor被訪問過了，就找下一個鄰接頂點(diǎn)
                neighbor = findNeighborByPriorNeighbor(vertex, neighbor);
            }
        }
        // 跳出循環(huán)，說明一條路走到底了，就應(yīng)該開始回溯，怎么回溯？
        // 其實(shí)外面再寫個方法，循環(huán)vertexList，讓每個未被訪問過的頂點(diǎn)都調(diào)用這個方法就好了
    }

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

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

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

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

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

• findNeighborByPriorNeighbor：這個方法是什么意思呢？比如我傳入的參數(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后面的那個鄰接頂點(diǎn)，即找到位置1后面的1第一次出現(xiàn)的位置的索引，顯然對應(yīng)的索引是5，在vertexList中對應(yīng)的是F。