LeetCode 例題精講 | 13 BFS 的使用場景：層序周遊、最短路徑問題

面向大象程式設計

DFS（深度優先搜尋）和 BFS（廣度優先搜尋）就像孿生兄弟，提到一個總是想起另一個。然而在實際使用中，我們用 DFS 的時候遠遠多于 BFS。那麼，是不是 BFS 就沒有什麼用呢？

如果我們使用 DFS/BFS 隻是為了周遊一棵樹、一張圖上的所有結點的話，那麼 DFS 和 BFS 的能力沒什麼差别，我們當然更傾向于更友善寫、空間複雜度更低的 DFS 周遊。不過，某些使用場景是 DFS 做不到的，隻能使用 BFS 周遊。這就是本文要介紹的兩個場景：「層序周遊」、「最短路徑」。

本文包括以下内容：

DFS 與 BFS 的特點比較
BFS 的适用場景
如何用 BFS 進行層序周遊
如何用 BFS 求解最短路徑問題

DFS 與 BFS

讓我們先看看在二叉樹上進行 DFS 周遊和 BFS 周遊的代碼比較。

DFS 周遊使用遞歸：

void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    dfs(root.left);
    dfs(root.right);
}

BFS 周遊使用隊列資料結構：

void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // Java 的 pop 寫作 poll()
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

隻是比較兩段代碼的話，最直覺的感受就是：DFS 周遊的代碼比 BFS 簡潔太多了！這是因為遞歸的方式隐含地使用了系統的棧，我們不需要自己維護一個資料結構。如果隻是簡單地将二叉樹周遊一遍，那麼 DFS 顯然是更友善的選擇。

雖然 DFS 與 BFS 都是将二叉樹的所有結點周遊了一遍，但它們周遊結點的順序不同。

DFS 與 BFS 對比

這個周遊順序也是 BFS 能夠用來解「層序周遊」、「最短路徑」問題的根本原因。下面，我們結合幾道例題來講講 BFS 是如何求解層序周遊和最短路徑問題的。

BFS 的應用一：層序周遊

LeetCode 102. Binary Tree Level Order Traversal 二叉樹的層序周遊（Medium）

給定一個二叉樹，傳回其按層序周遊得到的節點值。層序周遊即逐層地、從左到右通路所有結點。

什麼是層序周遊呢？簡單來說，層序周遊就是把二叉樹分層，然後每一層從左到右周遊：

二叉樹的層序周遊

乍一看來，這個周遊順序和 BFS 是一樣的，我們可以直接用 BFS 得出層序周遊結果。然而，層序周遊要求的輸入結果和 BFS 是不同的。層序周遊要求我們區分每一層，也就是傳回一個二維數組。而 BFS 的周遊結果是一個一維數組，無法區分每一層。

BFS 周遊與層序周遊的輸出結果不同

那麼，怎麼給 BFS 周遊的結果分層呢？我們首先來觀察一下 BFS 周遊的過程中，結點進隊列和出隊列的過程：

BFS 周遊的過程（動圖）

截取 BFS 周遊過程中的某個時刻：

BFS 周遊中某個時刻隊列的狀态

可以看到，此時隊列中的結點是 3、4、5，分别來自第 1 層和第 2 層。這個時候，第 1 層的結點還沒出完，第 2 層的結點就進來了，而且兩層的結點在隊列中緊挨在一起，我們無法區分隊列中的結點來自哪一層。

是以，我們需要稍微修改一下代碼，在每一層周遊開始前，先記錄隊列中的結點數量

（也就是這一層的結點數量），然後一口氣處理完這一層的

// 二叉樹的層序周遊
void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int n = queue.size();
        for (int i = 0; i < n; i++) { 
            // 變量 i 無實際意義，隻是為了循環 n 次
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }
}

這樣，我們就将 BFS 周遊改造成了層序周遊。在周遊的過程中，結點進隊列和出隊列的過程為：

BFS 層序周遊的過程（動圖）

可以看到，在 while 循環的每一輪中，都是将目前層的所有結點出隊列，再将下一層的所有結點入隊列，這樣就實作了層序周遊。

最終我們得到的題解代碼為：

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();

    Queue<TreeNode> queue = new ArrayDeque<>();
    if (root != null) {
        queue.add(root);
    }
    while (!queue.isEmpty()) {
        int n = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < n; i++) { 
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        res.add(level);
    }

    return res;
}

BFS 的應用二：最短路徑

在一棵樹中，一個結點到另一個結點的路徑是唯一的，但在圖中，結點之間可能有多條路徑，其中哪條路最近呢？這一類問題稱為最短路徑問題。最短路徑問題也是 BFS 的典型應用，而且其方法與層序周遊關系密切。

在二叉樹中，BFS 可以實作一層一層的周遊。在圖中同樣如此。從源點出發，BFS 首先周遊到第一層結點，到源點的距離為 1，然後周遊到第二層結點，到源點的距離為 2…… 可以看到，用 BFS 的話，距離源點更近的點會先被周遊到，這樣就能找到到某個點的最短路徑了。

層序周遊與最短路徑

小貼士：

很多同學一看到「最短路徑」，就條件反射地想到「Dijkstra 算法」。為什麼 BFS 周遊也能找到最短路徑呢？

這是因為，Dijkstra 算法解決的是帶權最短路徑問題，而我們這裡關注的是無權最短路徑問題。也可以看成每條邊的權重都是 1。這樣的最短路徑問題，用 BFS 求解就行了。

在面試中，你可能更希望寫 BFS 而不是 Dijkstra。畢竟，敢保證自己能寫對 Dijkstra 算法的人不多。

最短路徑問題屬于圖算法。由于圖的表示和描述比較複雜，本文用比較簡單的網格結構代替。網格結構是一種特殊的圖，它的表示和周遊都比較簡單，适合作為練習題。在 LeetCode 中，最短路徑問題也以網格結構為主。

最短路徑例題講解

LeetCode 1162. As Far from Land as Possible 離開陸地的最遠距離（Medium）

你現在手裡有一份大小為

的地圖網格
grid
，上面的每個單元格都标記為 0 或者 1，其中 0 代表海洋，1 代表陸地，請你找出一個海洋區域，這個海洋區域到離它最近的陸地區域的距離是最大的。

我們這裡說的距離是「曼哈頓距離」。

和

這兩個區域之間的距離是

如果我們的地圖上隻有陸地或者海洋，請傳回 -1。

這道題就是一個在網格結構中求最短路徑的問題。同時，它也是一個「島嶼問題」，即用網格中的 1 和 0 表示陸地和海洋，模拟出若幹個島嶼。

在上一篇文章中，我們介紹了網格結構的基本概念，以及網格結構中的 DFS 周遊。其中一些概念和技巧也可以用在 BFS 周遊中：

格子 (r, c) 的相鄰四個格子為： (r-1, c) 、 (r+1, c) 、 (r, c-1) 和 (r, c+1) ；
使用函數 inArea 判斷目前格子的坐标是否在網格範圍内；
将周遊過的格子标記為 2，避免重複周遊。

對于網格結構的性質、網格結構的 DFS 周遊技巧不是很了解的同學，可以複習一下上一篇文章：LeetCode 例題精講 | 12 島嶼問題：網格結構中的 DFS。

上一篇文章講過了網格結構 DFS 周遊，這篇文章正好講解一下網格結構的 BFS 周遊。要解最短路徑問題，我們首先要寫出層序周遊的代碼，仿照上面的二叉樹層序周遊代碼，類似地可以寫出網格層序周遊：

// 網格結構的層序周遊
// 從格子 (i, j) 開始周遊
void bfs(int[][] grid, int i, int j) {
    Queue<int[]> queue = new ArrayDeque<>();
    queue.add(new int[]{r, c});
    while (!queue.isEmpty()) {
        int n = queue.size();
        for (int i = 0; i < n; i++) { 
            int[] node = queue.poll();
            int r = node[0];
            int c = node[1];
            if (r-1 >= 0 && grid[r-1][c] == 0) {
                grid[r-1][c] = 2;
                queue.add(new int[]{r-1, c});
            }
            if (r+1 < N && grid[r+1][c] == 0) {
                grid[r+1][c] = 2;
                queue.add(new int[]{r+1, c});
            }
            if (c-1 >= 0 && grid[r][c-1] == 0) {
                grid[r][c-1] = 2;
                queue.add(new int[]{r, c-1});
            }
            if (c+1 < N && grid[r][c+1] == 0) {
                grid[r][c+1] = 2;
                queue.add(new int[]{r, c+1});
            }
        }
    }
}

以上的層序周遊代碼有幾個注意點：

隊列中的元素類型是 int[] 數組，每個數組的長度為 2，包含格子的行坐标和列坐标。
為了避免重複周遊，這裡使用到了和 DFS 周遊一樣的技巧：把已周遊的格子标記為 2。注意：我們在将格子放入隊列之前就将其标記為 2。想一想，這是為什麼？
在将格子放入隊列之前就檢查其坐标是否在網格範圍内，避免将「不存在」的格子放入隊列。

這段網格周遊代碼還有一些可以優化的地方。由于一個格子有四個相鄰的格子，代碼中判斷了四遍格子坐标的合法性，代碼稍微有點啰嗦。我們可以用一個

moves

數組存儲相鄰格子的四個方向：

int[][] moves = {
    {-1, 0}, {1, 0}, {0, -1}, {0, 1},
};

然後把四個 if 判斷變成一個循環：

for (int[][] move : moves) {
    int r2 = r + move[0];
    int c2 = c + move[1];
    if (inArea(grid, r2, c2) && grid[r2][c2] == 0) {
        grid[r2][c2] = 2;
        queue.add(new int[]{r2, c2});
    }
}

寫好了層序周遊的代碼，接下來我們看看如何來解決本題中的最短路徑問題。

這道題要找的是距離陸地最遠的海洋格子。假設網格中隻有一個陸地格子，我們可以從這個陸地格子出發做層序周遊，直到所有格子都周遊完。最終周遊了幾層，海洋格子的最遠距離就是幾。

從單個陸地格子出發的距離（動圖）

那麼有多個陸地格子的時候怎麼辦呢？一種方法是将每個陸地格子都作為起點做一次層序周遊，但是這樣的時間開銷太大。

BFS 完全可以以多個格子同時作為起點。我們可以把所有的陸地格子同時放入初始隊列，然後開始層序周遊，這樣周遊的效果如下圖所示：

從多個陸地格子出發的距離

這種周遊方法實際上叫做「多源 BFS」。多源 BFS 的定義不是今天讨論的重點，你隻需要記住多源 BFS 很友善，隻需要把多個源點同時放入初始隊列即可。

需要注意的是，雖然上面的圖示用 1、2、3、4 表示層序周遊的層數，但是在代碼中，我們不需要給每個周遊到的格子标記層數，隻需要用一個

distance

變量記錄目前的周遊的層數（也就是到陸地格子的距離）即可。

最終，我們得到的題解代碼為：

public int maxDistance(int[][] grid) {
    int N = grid.length;

    Queue<int[]> queue = new ArrayDeque<>();
    // 将所有的陸地格子加入隊列
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (grid[i][j] == 1) {
                queue.add(new int[]{i, j});
            }
        }
    }

    // 如果地圖上隻有陸地或者海洋，傳回 -1
    if (queue.isEmpty() || queue.size() == N * N) {
        return -1;
    }

    int[][] moves = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1},
    };

    int distance = -1; // 記錄目前周遊的層數（距離）
    while (!queue.isEmpty()) {
        distance++;
        int n = queue.size();
        for (int i = 0; i < n; i++) { 
            int[] node = queue.poll();
            int r = node[0];
            int c = node[1];
            for (int[] move : moves) {
                int r2 = r + move[0];
                int c2 = c + move[1];
                if (inArea(grid, r2, c2) && grid[r2][c2] == 0) {
                    grid[r2][c2] = 2;
                    queue.add(new int[]{r2, c2});
                }
            }
        }
    }

    return distance;
}

// 判斷坐标 (r, c) 是否在網格中
boolean inArea(int[][] grid, int r, int c) {
    return 0 <= r && r < grid.length 
        && 0 <= c && c < grid[0].length;
}

總結

可以看到，「BFS 周遊」、「層序周遊」、「最短路徑」實際上是遞進的關系。在 BFS 周遊的基礎上區分周遊的每一層，就得到了層序周遊。在層序周遊的基礎上記錄層數，就得到了最短路徑。

BFS 周遊是一類很值得反複體會和練習的題目。一方面，BFS 周遊是一個經典的基礎算法，需要重點掌握。另一方面，我們需要能根據題意分析出題目是要求最短路徑，知道是要做 BFS 周遊。

本文講解的隻是兩道非常典型的例題。LeetCode 中還有許多層序周遊和最短路徑的題目

層序周遊的一些變種題目：

LeetCode 103. Binary Tree Zigzag Level Order Traversal 之字形層序周遊
LeetCode 199. Binary Tree Right Side View 找每一層的最右結點
LeetCode 515. Find Largest Value in Each Tree Row 計算每一層的最大值
LeetCode 637. Average of Levels in Binary Tree 計算每一層的平均值

對于最短路徑問題，還有兩道題目也是求網格結構中的最短路徑，和我們講解的距離島嶼的最遠距離非常類似：

LeetCode 542. 01 Matrix
LeetCode 994. Rotting Oranges

還有一道在真正的圖結構中求最短路徑的問題：

LeetCode 310. Minimum Height Trees

LeetCode 例題精講 | 13 BFS 的使用場景：層序周遊、最短路徑問題

DFS 與 BFS

BFS 的應用一：層序周遊

BFS 的應用二：最短路徑

最短路徑例題講解

總結

繼續閱讀

計算機網絡：随機通路媒體通路控制之CSMA協定

迷宮最短路徑問題

UVa679（Dropping Balls）（二叉樹的編号）

面試題50. 樹中兩個結點的最低公共祖先結點

[leetcode] 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

bzoj1180 [CROATIAN2009]OTOCI

BZOJ 1180 [CROATIAN2009]OTOCI Link Cut Trees

WCF服務配置總結

luogu3384 【模闆】樹鍊剖分

bellman -ford算法的改進 spfa 算法

洛谷 P3806 【模闆】點分治1

BZOJ 3261: 最大異或和

hiho1063(樹型dp)

圖解

最短路徑->Dijkstra算法和Floyd算法

【TSP-GA】基于MATLAB的TSP-GA問題優化仿真