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

1. 是什么？

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

2. 圖的常用概念：

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

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

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

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

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

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

3. 圖的表示方式：

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

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

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

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

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

• 創(chuàng)建一個二維數(shù)組，用來保存頂點之間的邊，頂點與頂點之間有連線的用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; // 存放頂點
    private int[][] edges; // 鄰接矩陣，存放圖的邊
    private boolean[] isVisited; // 頂點是否被訪問

    /**
     * 構(gòu)造器
     * @param vertexCount 頂點的個數(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 頂點1
     * @param vertex2 頂點2
     * @param isConnected 頂點1和頂點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。先從初始頂點出發(fā)，訪問第一個鄰接頂點，然后再以這個被訪問到的鄰接頂點作為初始頂點，訪問它的第一個鄰接頂點?？梢岳斫鉃橐粭l路走到底，而不是把一個頂點的所有鄰接頂點先進行橫向訪問，而是縱向優(yōu)先，所以也叫深度優(yōu)先。

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

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

以開篇中的圖為例：

• 訪問A，并將A標記為已訪問；

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

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

第一個1對應的是B，所以A的第一個鄰接頂點是B，所以第二個遍歷出來的是B，并且標記B為已訪問；

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

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

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

• 找到C的第一個未被訪問的鄰接頂點，是D，打印D，并標記為已訪問；

• 找到D的第一個未被訪問的鄰接頂點，是H，打印H，并標記為已訪問；

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

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

• 回到C，找到C的第一個鄰接頂點D的后一個鄰接頂點：

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

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

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

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

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

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

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

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

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

private boolean[] isVisited; // 頂點是否被訪問

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

   /**
     * 查找頂點vertex的第一個鄰接頂點
     * @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對應的頂點就是vertex的鄰接頂點
            if (arr[i] == 1){
                return i;
            }
        }
        return -1;
    }

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

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

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

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

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

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

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

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

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