如果是遍歷一個(gè)數(shù)組，只需要從下標(biāo)0到下標(biāo)N-1循環(huán)就好了，遍歷一個(gè)鏈表只需要從頭指針開始直到?jīng)]有next為止，即使是遍歷一棵樹，也可以從根結(jié)點(diǎn)開始，按照前序、中序和后序等方式進(jìn)行。之所以可以這樣，是因?yàn)檫@些結(jié)構(gòu)都可以找到一個(gè)明確的起點(diǎn)，但圖不同。如下圖所示，有的人希望從A開始遍歷，有的人喜歡從C開始...，沒有辦法規(guī)定一個(gè)明確的起點(diǎn)。

圖

如果沒有策略，遍歷一個(gè)圖就像走迷宮一樣，有可能在一個(gè)結(jié)點(diǎn)停留多次，也可能有幾個(gè)結(jié)點(diǎn)永遠(yuǎn)不會(huì)訪問到。而圖的遍歷，通常有深度優(yōu)先和廣度優(yōu)先方式，接下來我們就看看這兩種方式是怎么做的，有什么區(qū)別。

深度優(yōu)先遍歷

深度優(yōu)先遍歷（Depth_First_Search）也稱為深度優(yōu)先搜索，簡稱為DFS。它是從圖中某個(gè)頂點(diǎn)v出發(fā)，訪問此頂點(diǎn)，然后從v的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到。對于非連通圖，只需要對它的連通分量分別進(jìn)行深度優(yōu)先遍歷即可。接下來我們以一個(gè)示例演示圖的深度優(yōu)先遍歷。如下圖所示：

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

在開始進(jìn)行遍歷之前，我們還要準(zhǔn)備一個(gè)數(shù)組，用來記錄已經(jīng)訪問過的元素。其中0代表未訪問，1代表已訪問，如下所示：

visited數(shù)組

為了便于演示，假設(shè)我們是在走迷宮，A是入口，每次都向右手邊前進(jìn)。首先從A走到B，結(jié)果如下：

A-B

B之后有三個(gè)路，我們依然選擇最右邊，如此下去，直到走到F，如下所示：

B-F

到達(dá)F后，如果我們繼續(xù)按照向右走的原則，就會(huì)再次訪問A，此時(shí)我們訪問除了A后的最右側(cè)通道，也就是訪問G，如下所示：

F-G

到達(dá)G后，可以發(fā)現(xiàn)B和D都走過了，這時(shí)候走到H，如下所示：

G-H

到達(dá)H后，可以發(fā)現(xiàn)D和E都走過了，也就是說走到了盡頭，但是并不代表所有的頂點(diǎn)都訪問過了，因?yàn)槌俗钣覀?cè)頂點(diǎn)，每個(gè)頂點(diǎn)還可能和更多的頂點(diǎn)連通，所以我們從H退回到G，發(fā)現(xiàn)全部走過了，再向前退回到F，也全部走過了，直到退回到B時(shí)，發(fā)現(xiàn) I 還沒走過，于是訪問頂點(diǎn) I，如下所示：

B-I

同理，訪問 I 之后，發(fā)現(xiàn)與 I 連通的頂點(diǎn)都訪問過了，所以再向前回退，直到回到頂點(diǎn)A，發(fā)現(xiàn)全部頂點(diǎn)都訪問過了，至此遍歷完畢。

廣度優(yōu)先遍歷

深度優(yōu)先遍歷可以認(rèn)為是縱向遍歷圖，而廣度優(yōu)先遍歷（Breadth_First_Search）則是橫向進(jìn)行遍歷。還以上圖為例，不過為了方便查看，我們把上圖調(diào)整為如下樣式：

廣度優(yōu)先遍歷圖

我們依然以A為起點(diǎn)，把和A鄰接的B和F放在第二層，把和B、F鄰接的C、I、G、E放在第三層，剩下的放在第四層。廣度優(yōu)先遍歷就是從上到下一層一層進(jìn)行遍歷，這和樹的層序遍歷很像。我們依然借助一個(gè)隊(duì)列來完成遍歷過程，因?yàn)楹蜆涞膶有虮闅v很像，這里只展示結(jié)果，如下所示：

廣度優(yōu)先遍歷隊(duì)列

對于非連通圖，依然通過visited數(shù)組來進(jìn)行判斷即可。

代碼實(shí)現(xiàn)

圖的存儲(chǔ)方式有很多種，但是用來實(shí)現(xiàn)遍歷的思路是一致的，我們以鄰接矩陣為例，給出DFS和BFS的參考實(shí)現(xiàn)。

深度優(yōu)先遍歷實(shí)現(xiàn)

private void DFS(int i) {
    // 標(biāo)記當(dāng)前元素已經(jīng)訪問
    visited[i] = true;
    System.out.println("當(dāng)前訪問頂點(diǎn)：" + getVertexByIndex(i));

    int next = getFirstNeighbor(i);

    while (next != -1) {
        if (!visited[next]) {
            DFS(next);
        }
        next = getNextNeighbor(i, next);

    }
}

public void DFS() {
    for (int i = 0; i < vertexList.size(); i++) {
        visited[i] = false;
    }
    // 非連通圖，不同的連通分量要單獨(dú)進(jìn)行DFS
    for (int i = 0; i < vertexList.size(); i++) {
        if (!visited[i]) {
            DFS(i);
        }
    }
}

廣度優(yōu)先遍歷實(shí)現(xiàn)

private void BFS(int i) {
    // 標(biāo)記當(dāng)前元素已經(jīng)訪問
    visited[i] = true;
    System.out.println("當(dāng)前訪問頂點(diǎn)：" + getVertexByIndex(i));

    int cur, next;
    LinkedList<Integer> queue = new LinkedList<>();
    queue.addLast(i);
    while (!queue.isEmpty()) {
        cur = queue.removeFirst();
        next = getFirstNeighbor(cur);
        while (next != -1) {
            if (!visited[next]) {
                // 標(biāo)記當(dāng)前元素已經(jīng)訪問
                visited[next] = true;
                System.out.println("當(dāng)前訪問頂點(diǎn)：" + getVertexByIndex(next));
                queue.addLast(next);
            }
            next = getNextNeighbor(cur, next);
        }
    }
}

public void BFS() {
    for (int i = 0; i < vertexList.size(); i++) {
        visited[i] = false;
    }
    for (int i = 0; i < vertexList.size(); i++) {
        if (!visited[i]) {
            BFS(i);
        }
    }
}

完整代碼已上傳至我的github。

我是飛機(jī)醬，如果您喜歡我的文章，可以關(guān)注我~

編程之路，道阻且長。唯，路漫漫其修遠(yuǎn)兮，吾將上下而求索。