专题 12图论入门：BFS、DFS 与拓扑排序

12.1图题只需要三块积木

很多人被「图论」二字吓到，以为要学邻接矩阵、最短路、并查集一大堆。其实力扣里 90% 的图题，骨架都一样：

网格题 = 隐式图

最常见的一类是「二维字符网格」题（岛屿、橘子、迷宫）。这时每个格子就是图的一个节点，相邻格子（上下左右）就是边。 你不需要 new 一个 Graph 类——grid[i][j] 本身就是节点，四方向偏移就是邻边：

// 四方向偏移：上、右、下、左（顺序随意，统一即可）
int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

// 从 (x, y) 出发，枚举四个邻居
for (int[] d : dirs) {
    int nx = x + d[0];
    int ny = y + d[1];
    // 先判断越界，再判断是否可走 / 未访问
    if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
        // (nx, ny) 是一个合法邻居
    }
}

visited 的两种存法

• 另开一个 boolean[][] visited：最直观，和原网格分开，适合「原网格还要保留值」的情况。
• 直接改原网格：比如把访问过的陆地改成海洋（'0'）、把新鲜橘子改成腐烂。省空间，但前提是原题不再需要原值（见 12.2「沉岛」技巧）。

下面三道题，就是这三块积木的不同组合：DFS 洪水填充（岛屿）、多源 BFS（橘子）、入度表 + 队列（课程表拓扑排序）。

12.2岛屿数量：DFS 洪水填充（中等，力扣 200）

中等 核心：遍历格点 + 沉岛

题意：给你一个 '1'（陆地）和 '0'（水）的二维网格，相连的陆地（上下左右）组成一个岛。求岛屿个数。 例如下方有 3 个岛：

1 1 0 0 0
1 0 0 1 1
0 0 0 1 1
（左上的 1 是一个岛，右下的四个 1 是另一个岛，共 2 个）

思路推导

岛屿是「连成一片的陆地」。思考方式：每发现一块没访问过的陆地，它一定属于某个岛；从这个点出发，把所有和它相连的陆地都「标记掉」，岛数 +1。

怎么把「相连的陆地都标记掉」？这就是洪水填充（flood fill）——从一个陆地格出发，DFS 四个方向：碰到陆地就继续深入，碰到水/边界/已访问就停。一次 DFS 能「淹掉」一整座岛（把所有陆地改成 '0'，即「沉岛」，顺便充当 visited）。 整张网格扫一遍，每遇到一个仍是 '1' 的格，就是一座新岛的起点，触发一次 DFS。

为什么用 DFS 而不是 BFS？这里只关心「连通性」（一座岛算一个），不关心距离/层数，DFS 用递归写最简洁。换成 BFS 也完全正确，只是代码稍长。

参考代码

class Solution {
    // 四方向：上、右、下、左
    int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {     // 发现一座未访问的岛
                    count++;
                    dfs(grid, i, j);         // 一次性淹掉整座岛
                }
            }
        }
        return count;
    }

    // 洪水填充：把 (i,j) 连通的所有陆地都改成 '0'（沉岛=标记已访问）
    private void dfs(char[][] grid, int i, int j) {
        // 越界 或 不是陆地（已是水/已沉），直接返回
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length
                || grid[i][j] != '1') {
            return;
        }
        grid[i][j] = '0';                    // 沉岛：标记当前陆地已访问
        for (int[] d : dirs) {               // 向四个方向扩散
            dfs(grid, i + d[0], j + d[1]);
        }
    }
}

复杂度：时间 O(m×n)，每个格子最多被访问一次（沉岛后不会再进 DFS）；空间 O(m×n)（最坏递归深度等于格子总数，如全陆地时一条斜线递归）。

亲手走一遍：grid = [[1,1,0],[1,0,0],[0,0,1]]

初始扫描：
(0,0)='1' -> 触发 DFS，开始沉岛
  dfs(0,0): 沉(0,0)；邻居(0,1),(1,0) 是'1'继续沉
    dfs(0,1): 沉(0,1)；邻居(0,0)已沉、(0,2)='0'停、(1,1)='0'停
    dfs(1,0): 沉(1,0)；邻居(0,0)已沉、(2,0)='0'停、(1,1)='0'停
  这次 DFS 把左上角三块陆地全沉了 -> count=1
继续扫描：
(0,1)(1,0) 已是'0'跳过；(2,2)='1' -> 触发第二次 DFS，沉掉它 -> count=2
最终 count = 2（左上岛 + 右下角单独一块）。

可以看到：一次从 (0,0) 出发的 DFS，顺着连通性把整座左上岛「淹」光了，count 只 +1； 之后扫描遇到右下角孤立的 (2,2) 是另一座岛，再 +1。这正是「每发现一个未访问陆地就数一座岛、并沉掉整座」的体现。

12.3腐烂的橘子：多源 BFS（中等，力扣 994）

中等 核心：多个起点同时入队，层数 = 分钟数

题意：网格里 2 表示腐烂橘子、1 表示新鲜橘子、0 表示空格。每分钟，每个腐烂橘子会把它上下左右相邻的新鲜橘子传染腐烂。 求多少分钟后所有橘子都烂；若不可能（有新鲜橘子永远接触不到腐烂橘子），返回 -1。 例如 [[2,1,1],[1,1,0],[0,1,1]]，需要 4 分钟。

思路推导

这道题和岛屿的区别：岛屿只数「连通块个数」，不关心距离；这里关心「几分钟」，也就是距离/层数。 一提到「扩散 + 层数/最短时间」就该想到 BFS——BFS 天然一层层扩散，层数就是时间。

关键在「多个起点」：初始时可能不止一个腐烂橘子。如果只从一个腐烂橘子 BFS，会漏掉别的源头。 正确做法：把所有初始腐烂橘子同时入队（多源 BFS），第 0 层就是它们全体。 然后正常 BFS：每出队一个腐烂橘子，把它相邻的新鲜橘子变腐烂并入队，同时记录「这一层处理完代表过了 1 分钟」。

怎么数分钟？用一个「层」的概念：每开始处理新一层前，记下当前队列大小 sz，把这 sz 个节点（同一分钟的）全处理完，分钟数 +1。 或者用 int[] 存坐标+分钟 入队也行。处理完后，再扫一遍网格：若还有新鲜橘子（'1'）残留，说明有橘子永远烂不到，返回 -1。

参考代码

class Solution {
    int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Queue<int[]> q = new LinkedList<>();
        int fresh = 0;                       // 统计新鲜橘子总数
        // 把所有初始腐烂橘子入队（多源起点），并数新鲜橘子
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) q.offer(new int[]{i, j});
                if (grid[i][j] == 1) fresh++;
            }
        }
        if (fresh == 0) return 0;            // 本来就没新鲜橘子，0 分钟

        int minutes = 0;
        while (!q.isEmpty()) {
            int sz = q.size();               // 当前层的节点数（同一分钟的腐烂橘子）
            boolean changed = false;         // 这一层是否真的传染了
            for (int k = 0; k < sz; k++) {
                int[] cur = q.poll();
                for (int[] d : dirs) {
                    int nx = cur[0] + d[0], ny = cur[1] + d[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n
                            && grid[nx][ny] == 1) {      // 相邻的新鲜橘子
                        grid[nx][ny] = 2;               // 传染腐烂
                        fresh--;                        // 新鲜数 -1
                        changed = true;
                        q.offer(new int[]{nx, ny});     // 新腐烂的入队，下一层再扩散
                    }
                }
            }
            if (changed) minutes++;          // 这一层确实传染了，才计 1 分钟
        }
        // 若还有新鲜橘子残留，说明永远烂不到
        return fresh == 0 ? minutes : -1;
    }
}

复杂度：时间 O(m×n)（每个橘子最多入队一次），空间 O(m×n)（队列最坏存所有橘子）。

亲手走一遍：grid = [[2,1,1],[1,1,0],[0,1,1]]

初始：腐烂点 (0,0) 入队；新鲜橘子共 6 个（(0,1)(0,2)(1,0)(1,1)(2,1)(2,2)，fresh=6）。

第 0 层（mins=0）：队列=[(0,0)]，sz=1
  处理(0,0)：传染(0,1)、(1,0) -> 变2，fresh=4，入队
  changed=true -> minutes=1

第 1 层（mins=1）：队列=[(0,1),(1,0)]，sz=2
  处理(0,1)：传染(0,2) -> 变2，fresh=3
  处理(1,0)：邻居(1,1)仍是新鲜 -> 变2，fresh=2
  入队(0,2),(1,1)；changed=true -> minutes=2

第 2 层（mins=2）：队列=[(0,2),(1,1)]，sz=2
  处理(0,2)：四周皆0/已烂，无新传染
  处理(1,1)：传染(2,1) -> 变2，fresh=1，入队(2,1)
  changed=true -> minutes=3

第 3 层（mins=3）：队列=[(2,1)]，sz=1
  处理(2,1)：传染(2,2) -> 变2，fresh=0，入队(2,2)
  changed=true -> minutes=4

第 4 层（mins=4）：队列=[(2,2)]，sz=1
  处理(2,2)：四周无新鲜，无传染；changed=false（分钟不+1）
队列空。fresh=0 == 0 -> 返回 4 分钟。

逐层数下来，新鲜橘子 6 个被分 4 层全部传染完，返回 4。注意「changed 才加分钟」：最后一层若没真传染，不会多算。 若把某个新鲜橘子改成永远接触不到腐烂点（比如左上角孤立一块 1），fresh 就减不到 0，最终返回 -1。

12.4课程表：拓扑排序（中等，力扣 207）

中等 核心：入度表 + 邻接表 + 队列

题意：numCourses 门课，prerequisites[i] = [a, b] 表示要选 a 必须先选 b（b 是 a 的先修）。问能否学完所有课（即是否存在一个合法选课顺序，无环）。 例如 numCourses=2, prerequisites=[[1,0]]，先修 0 再选 1，可以，返回 true；若有 [1,0] 和 [0,1] 互相先修，则 false。

思路推导

这是标准的拓扑排序问题：把课看成节点，先修关系看成有向边 b → a（b 指向 a，表示 b 要先完成）。 能学完所有课 ⇔ 图里没有环。拓扑排序就是「把节点排成一条线，让所有边都从前指向后」；若存在环，就排不出。

怎么做？用入度表 + 队列的 BFS 写法（Kahn 算法）：

• 入度（indegree）：一门课有多少门先修课。indegree[a] 表示有几门课是 a 的前置。
• 邻接表（graph）：graph[b] 存「b 完成后能解锁的课」（即所有以 b 为先修的课）。
• 把所有入度为 0 的课（没有先修、可以直接学的）入队。
• 每次出队一门课 u，就「学完」它；遍历 graph[u]，把 u 解锁的每门课 v 的入度 -1。 当某门 v 的入度减到 0，说明它的先修都学完了，v 入队。
• 最终若学完的课数 == 总课数，说明无环、能学完（true）；否则有环（false）。

「入度归零 = 先修课都完成」是这题的核心直觉：一门课的入度就是它还没完成的先修数量，归零意味着前置全部就绪，可以学了。

参考代码

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // indegree[i]：第 i 门课还有几门先修没完成
        int[] indegree = new int[numCourses];
        // graph[i]：学完 i 后，能解锁哪些课（i 是它们的先修）
        List<Integer>[] graph = new List[numCourses];
        for (int i = 0; i < numCourses; i++) graph[i] = new ArrayList<>();

        for (int[] p : prerequisites) {
            int a = p[0], b = p[1];          // 学 a 要先学 b
            graph[b].add(a);                 // b 完成后解锁 a
            indegree[a]++;                   // a 的先修数 +1
        }

        // 所有入度为 0 的课（无先修）先入队
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) q.offer(i);
        }

        int learned = 0;                     // 已学完的课数
        while (!q.isEmpty()) {
            int u = q.poll();
            learned++;                       // 学完 u
            for (int v : graph[u]) {         // u 解锁的每门课 v
                indegree[v]--;               // v 的一个先修已完成
                if (indegree[v] == 0) {      // v 的先修全部完成
                    q.offer(v);
                }
            }
        }
        // 学完的课数 == 总课数 才说明无环、能全部学完
        return learned == numCourses;
    }
}

复杂度：时间 O(V + E)（V 门课、E 条先修边，每点每边各处理一次），空间 O(V + E)（邻接表 + 入度数组）。

亲手走一遍：numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]

含义：1 需先 0、2 需先 0、3 需先 1、3 需先 2。即 0 是 1 和 2 的先修，1 和 2 是 3 的先修。

建表：
  graph[0]=[1,2]   indegree[1]=1
  graph[1]=[3]     indegree[2]=1
  graph[2]=[3]     indegree[3]=2
  graph[3]=[]      indegree[0]=0
入度为 0 的：只有 0 -> 队列=[0]

出队 0：learned=1；解锁 graph[0]=[1,2]
  indegree[1]:1->0 -> 入队；indegree[2]:1->0 -> 入队。队列=[1,2]
出队 1：learned=2；解锁 graph[1]=[3]
  indegree[3]:2->1（还没到0，不入队）。队列=[2]
出队 2：learned=3；解锁 graph[2]=[3]
  indegree[3]:1->0 -> 入队。队列=[3]
出队 3：learned=4；graph[3]=[] 无解锁。队列空。

learned(4) == numCourses(4) -> 无环，返回 true。
合法顺序之一：0 -> 1 -> 2 -> 3（或 0 -> 2 -> 1 -> 3）。

对比有环的情形：prerequisites=[[1,0],[0,1]]。建表后 indegree[0]=1、indegree[1]=1，没有任何入度为 0 的课能入队， 队列一开始就空，learned=0 ≠ 2，返回 false——环被准确识别。这就是「入度归零 = 先修全完成」的威力。

补充：拓扑排序还有「DFS 三色标记」写法

除了上面的 BFS（Kahn）写法，拓扑排序也能用 DFS 做：给每个节点标三种颜色——

• 白色（0）：还没访问过；
• 灰色（1）：正在当前 DFS 路径上（已入栈、还没回溯完）；
• 黑色（2）：已经完全处理完（出栈）。

DFS 时若遇到灰色节点，说明「从它出发又走回它自己」，即存在后向边 = 有环，直接返回 false；遇到黑色说明之前已安全处理过，跳过；白色则继续递归。 这种写法在「判断有向图是否 DAG」时很常用，但面试里 BFS（Kahn）因为「顺手能输出顺序、入度表直观」而更推荐首选。 两种方法本质等价，知道有这一支即可，不必强背。

12.5BFS / DFS 怎么选

这两兄弟都是遍历，但适用场景不同。一张表记清：

12.6本专题常见坑