图系列第 6 篇：BFS/DFS 的应用——连通分量、二分图与环

嘿，朋友，欢迎回到图系列。这是第 6 篇，主题只有一个：遍历学完之后，到底能干什么？

前两篇我们分别学了广度优先搜索 BFS 和深度优先搜索 DFS。第 4 篇里，我们认识了 BFS 的水波式扩散：队列逐层推进，第一次到达某个顶点的路径一定是最短的，所以它在无权图最短路径、层序遍历这些场景里大显身手。第 5 篇里，我们认识了 DFS 的探险家精神：一条路走到黑、走不动就回头，配合递归和显式栈两种姿势，再加上 DFS 树和时间戳，把图的深层次结构摸得清清楚楚。如果这两篇的内容你还有点生疏，建议先回头把第 4、5 篇读一遍再来，因为今天所有应用都建立在同一个基本功上：用 visited 数组保证每个顶点只访问一次，然后按照某种顺序把整个图扫一遍。

遍历本身看起来只是”把所有顶点走一遍”，好像没什么了不起。但真正把图论用于解决问题的关键，恰恰就在于遍历过程中我们顺便记录了什么、发现了什么。同样是走一遍图，你可以在进入每个新分量时计数，从而得到连通分量的数量；可以在访问邻居时检查颜色是否冲突，从而判断图能不能二分；可以在看到”回头路”时识别出环的存在；也可以把”从某个点出发能到达的所有位置”看成一片连续区域，从而实现画图软件里的油漆桶。这四个问题——连通分量统计、二分图判定、环检测、洪水填充——就是今天的主角，它们也是后续很多高级算法的地基：第 7 篇的拓扑排序依赖环检测，第 15 篇的二分图匹配依赖染色判定，而并查集那套思路在树系列里我们虽然见过，但今天你会看到遍历其实也能干净利落地解决同一类问题。

在出发之前，先给你一个动手的机会。下面的可视化实验室可以让你在浏览器里实际搭建图、跑 BFS 和 DFS，观察访问顺序、分量划分和染色结果。看完这一篇的每个算法，都建议回去玩一玩：纸上得来终觉浅，绝知此事要躬行。

好，思路已就位，我们按”先简单后复杂”的顺序出发。第一个应用是最直观、也最常用的连通分量统计。

1 应用一：连通分量统计

1.1 什么是连通分量

在无向图里，如果两个顶点之间存在一条路径，我们就说这两个顶点是连通的。连通关系有一个非常重要的性质：它是一个等价关系。换句话说，它满足三条规则：任何一个顶点都和自己连通（自反性）；如果 A 和 B 连通，那么 B 和 A 也连通（对称性）；如果 A 和 B 连通，B 和 C 连通，那么 A 和 C 也连通（传递性）。等价关系会把集合中的元素划分成互不相交的等价类，在无向图里，这些等价类就叫连通分量，英文是 Connected Component。

你可以把一张无向图想象成由若干座”岛屿”组成的群岛：同一座岛上的任意两个城市之间都能通过岛上的道路互相到达；不同岛上的城市之间则没有任何通路，除非你坐飞机（也就是加一条新边）。每一座岛就是一个连通分量。下面这张图一共有四个连通分量，注意看顶点之间的边完全被”切开”了：

graph TD
    subgraph C1["分量 1"]
        A["A"] --- B["B"]
        B --- C["C"]
        A --- C
    end
    subgraph C2["分量 2"]
        D["D"] --- E["E"]
        D --- F["F"]
    end
    subgraph C3["分量 3"]
        G["G"] --- H["H"]
        G --- I["I"]
        H --- I
    end
    subgraph C4["分量 4"]
        J["J"]
    end

图上一共有 10 个顶点，但它们并不在同一个连通世界里：A、B、C 是一伙的，D、E、F 是一伙的，G、H、I 是一伙的，而 J 孤零零一个人也算一个分量。注意 J 这个例子很关键：单个没有边的顶点也是一个合法的连通分量，因为连通分量的定义只要求”分量内部彼此可达”，一个顶点的分量内部当然满足条件。很多初学者在数分量时会漏掉这种孤立点，写代码时如果外层循环覆盖不到它们，就会得到错误的答案。

那么，怎么用遍历来统计连通分量呢？思路简单得令人惊讶：从每个还没有被访问过的顶点出发，分别做一次 BFS 或 DFS。每一次新的遍历开始，就说明我们进入了一个全新的连通分量，计数器加一。 这是因为，如果某个顶点和已经访问过的顶点连通，那么它早该在之前的某次遍历中被访问到了；它既然还没被访问，就必然属于另一个全新的分量。于是”做了几次外层遍历”和”图里有几个连通分量”严格相等。

1.2 外层循环的遍历框架

把这个想法写成代码，就是我们今天所有应用的通用骨架。以邻接表存储的无向图为例，用 DFS 做内层遍历时是这样：

def dfs(adj, visited, u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(adj, visited, v)

def count_components(adj, n):
    visited = [False] * n
    components = 0
    for u in range(n):
        if not visited[u]:
            components += 1
            dfs(adj, visited, u)
    return components

代码短得不像话，但每一步都有讲究。外层 for 循环从 0 扫到 n-1，对每个顶点问一句”你访问过吗”；如果答案是”没有”，就说明它是某个未发现分量的第一个顶点，于是计数器加一，然后从这个顶点启动一次完整的 DFS，把整个分量里所有顶点全部标记为已访问。等这次 DFS 返回，这个分量就被彻底”圈”完了，外层循环继续往下扫，遇到的下一个未访问顶点必然属于下一个分量。

把内层遍历换成 BFS 也完全一样，只要把 dfs 换成基于队列的 bfs，外层结构一字不改：

from collections import deque

def bfs(adj, visited, start):
    q = deque([start])
    visited[start] = True
    while q:
        u = q.popleft()
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                q.append(v)

def count_components_bfs(adj, n):
    visited = [False] * n
    components = 0
    for u in range(n):
        if not visited[u]:
            components += 1
            bfs(adj, visited, u)
    return components

为什么两种遍历都行？因为统计分量这件事只关心”哪些顶点彼此可达”，不关心访问的具体顺序。BFS 一层层扩散也好，DFS 一条路钻到底也罢，只要一次遍历能够把起始点所在的整个分量全部标记，外层的计数逻辑就成立。这个”外层循环 + 内层遍历”的模式太常用了，值得记住：凡是要处理图中每一个独立组成部分的问题，几乎都能套这个骨架。 稍后你会看到，二分图判定就是在内层遍历中顺便染色，环检测则是在内层遍历中检查特殊边。

复杂度也一目了然：每个顶点恰好被访问一次，每条边最多被检查两次（无向图中边 (u,v) 在 u 的邻接表里检查一次、在 v 的邻接表里再检查一次），所以总时间是 O(V+E)，空间是 O(V)（visited 数组加递归栈或队列）。这个复杂度几乎是图算法里能拿到的最好的量级了——你至少要把每条边读一遍才能知道图长什么样，所以线性时间就是这类问题的”理论下限附近”。

1.3 经典题：岛屿数量

理论讲完，立刻上一个家喻户晓的实战题：岛屿数量。题目是这样的：给你一个 m 行 n 列的二维网格，网格里只有两种值，1 表示陆地，0 表示海水。如果两个 1 在水平方向或垂直方向上相邻，它们就算同一块陆地；请数一数一共有多少座岛屿。

这句话翻译成图论语言就是：把每个 1 格子看成一个顶点；两个上下左右相邻的 1 之间连一条边。这样一来，“同一座岛”恰好就是”同一个连通分量”，问题退化成我们刚学过的分量统计。下面这张图展示了一个 5×5 的网格，里面有三座岛屿，注意右上方那座岛由三个格子组成一个 L 形，而右下角的单个 1 也是一座独立的岛：

graph TD
    subgraph 岛屿一
        A["(0,0)"] --- B["(0,1)"]
        B --- C["(1,1)"]
    end
    subgraph 岛屿二
        D["(2,0)"] --- E["(2,1)"]
        E --- F["(3,1)"]
        F --- G["(4,1)"]
    end
    subgraph 岛屿三
        H["(2,3)"]
    end

（为了方便画图，这里把每个格子标成了坐标；网格里的海水格子没有出现在图中，因为它们不对应任何顶点。）如果把这个网格画成完整的坐标平面，你会看到 (0,0) 和 (0,1) 相邻所以连边，(0,1) 和 (1,1) 相邻所以也连边，于是它们构成第一座岛。坐标 (2,3) 虽然看起来离第二座岛不远，但上下左右都没有 1 和它相邻，所以它只能孤零零地自成一座。

实现的时候，我们不必真的去建邻接表——网格本身就是一种天然的图。一个格子的邻居就是它上下左右四个方向的格子，检查时只需要注意别越界。常见的写法有两种：一种是准备一个和网格同样大小的 visited 二维数组；另一种更省事的做法是原地把访问过的陆地改成海水，用 0 覆盖 1，这样既起到了 visited 的作用，又不用额外开数组。面试和竞赛里两种写法都有人用，原地修改更简洁，但要记得先跟面试官确认网格是否允许修改。

DFS 版本的核心代码长这样：

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != '1':
            return
        grid[r][c] = '0'          # 标记为已访问：原地淹掉这块陆地
        dfs(r - 1, c)
        dfs(r + 1, c)
        dfs(r, c - 1)
        dfs(r, c + 1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1        # 发现一座新岛屿
                dfs(r, c)         # 把整座岛淹掉
    return count

dfs 的开头做了两件事：先检查坐标是否越界，再检查当前格子是不是陆地。这两个检查的顺序很重要，因为一旦越界，后面访问 grid[r][c] 就会出错。把四个方向的递归写出来之后，整个函数就像潮水一样把一座岛完整淹没：从发现的那块陆地出发，把所有连在一起的陆地全部变成海水，下一次外层循环再遇到 1 时，一定是另一座全新岛屿。

用 BFS 写也毫不含糊，只是把递归换成了队列，并且要在一个格子入队的那一刻就标记为海水，而不是出队时再标记。这个细节我们在第 4 篇讲过：如果出队才标记，同一个格子可能被多个邻居重复加入队列，虽然最终答案通常不受影响，但队列会膨胀、性能会下降，极端情况下甚至可能超时。正确的姿势是入队即标记。

from collections import deque

def num_islands_bfs(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                q = deque([(r, c)])
                grid[r][c] = '0'
                while q:
                    x, y = q.popleft()
                    for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1':
                            grid[nx][ny] = '0'
                            q.append((nx, ny))
    return count

岛屿数量的复杂度同样是 O(m×n)：每个格子最多被访问常数次，四个方向的邻居检查也都是常数工作。空间上，BFS 的队列最坏可能装下整座岛，DFS 的递归栈在极端情况下（比如整张网格全是陆地）深度也能达到 O(m×n)，所以两者最坏空间都是 O(m×n)。递归版本在网格特别大时要小心 Python 默认的递归深度限制，必要时改用 BFS 或显式栈。

1.4 连通分量统计还能用在哪儿

岛屿数量只是冰山一角。连通分量统计在现实世界里的应用随处可见：社交网络里，把用户当顶点、把”互相关注”当边，一个连通分量就是一个”联系紧密的圈子”，产品经理可以用它来识别社群结构；计算机网络里，把路由器当顶点、把物理链路当边，连通分量统计可以回答”整个网络是不是连成一片”这个基础问题，如果分量数量大于一，就说明网络被切成了互不相通的好几块，任何跨块的通信都会失败；在图像处理里，把像素当顶点、把”颜色相近且相邻”当边，连通分量恰好就是图像里的一处处目标区域，可以用来做物体计数；在程序分析里，把函数调用关系画成图，一个连通分量就是一组互相调用的函数，编译器和链接器常常需要知道它们。

甚至还有一个很经典的面试变体：给你一个无向图，问”最少加几条边可以让整个图变成连通图”。答案就是连通分量数减一——把每一座岛的任意一个顶点和另一座岛的任意一个顶点用一条新边连起来，连成一条链，n 个分量只需要 n-1 条边。你看，一旦把分量统计做出来，很多看起来高级的问题立刻变得很简单。

不过要注意，上面说的连通分量都是指无向图。有向图里的连通性更复杂，顶点之间可以单向可达、也可以双向可达，所以有向图有”弱连通分量”和”强连通分量”之分，后者需要用 Tarjan 算法或者 Kosaraju 算法来求，那已经超出了今天的外层循环框架，我们留到图系列后面专门讲强连通分量的时候再展开。今天你只要牢牢记住：无向图的连通分量 = 外层循环里发起遍历的次数。

2 应用二：二分图判定（染色法）

2.1 什么是二分图

第二个应用依然非常经典：判断一张图是不是二分图。二分图（Bipartite Graph）的定义是这样的：存在一种方式把顶点分成左右两组，使得每条边的两个端点分别落在不同的组里。换句话说，图中所有边都必须是”跨组边”，组内部不允许出现任何边。

你可以把二分图想象成一场相亲晚宴：左边坐着一排嘉宾，右边坐着另一排嘉宾，每一对互相心动的男女之间连一条线，但心动只会发生在左右两组之间，同组的人之间没有连线。任何满足”边只存在于两组之间”的图，不管它有多少个顶点、多少条边，都是一张合法的二分图。实际生活中二分图出现的频率高得惊人：电影和演员的关系（演员只演电影，电影只被演员演）、课程和学生选课的关系、工人和岗位的匹配关系，全部天然是二分图，因为实体分属两个不同类型，关系只会在不同类型之间产生。

那么，怎么判断一张图是不是二分图呢？最自然的想法就是染色：给每个顶点涂一种颜色，一共只用两种颜色，要求相邻顶点颜色必须不同。如果整张图都能做到”相邻即异色”，那两种颜色自然就把顶点分成了两组，图就是二分图；如果无论如何都做不到，图就不是二分图。下面这张图就成功染上了两种颜色，红色顶点全部在左侧、蓝色顶点全部在右侧，每条边的两端颜色都不同：

graph LR
    subgraph 左组
        A["A（红）"]
        B["B（红）"]
    end
    subgraph 右组
        C["C（蓝）"]
        D["D（蓝）"]
        E["E（蓝）"]
    end
    A --- C
    A --- D
    B --- C
    B --- E

注意看这张图里的结构：A 和 B 都只和 C、D、E 相连，C、D、E 之间没有任何边，所以红蓝两组互不干扰，染色一气呵成。这其实就是把”分组”的问题翻译成了”染色”的问题——判断二分图，本质上就是问：能不能用两种颜色给所有顶点染色，使每条边两端异色？

2.2 染色算法：BFS 和 DFS 都能干

染色算法和连通分量统计长得非常像，仍然是那个熟悉的外层循环加内层遍历，只是这次遍历时多带一个”任务”：给当前顶点分配颜色，并检查邻居的颜色是否和它冲突。

具体做法如下。先准备一个颜色数组 color，用 0 表示还没染，1 和 2 表示两种颜色。外层循环扫描所有顶点，遇到没染色的顶点就启动一次遍历。在遍历中，从起始顶点开始，把它染成颜色 1；每访问一个顶点 u，就检查它的每一个邻居 v：如果 v 还没染色，就把它染成与 u 相反的颜色（1 的反面是 2，2 的反面是 1）；如果 v 已经染色了，就检查它的颜色是否等于 u 的颜色——如果相等，说明出现了冲突，整张图不是二分图，可以立刻宣布失败并停止。

为什么这样贪心地染色一定正确？因为图不一定是连通的，但每个连通分量内部的关系是独立传播的：起始点染成颜色 1 之后，它所有邻居被迫染成 2，邻居的邻居被迫染回 1，颜色像声波一样沿边一层层传播，任何顶点只要在同一个分量里，它的颜色就被唯一地决定了——除非在传播过程中撞见矛盾。外层循环保证每个分量都有它的”初始染色点”，所以整个算法覆盖了所有顶点。

用 BFS 实现时，队列里除了顶点本身，通常还要带上它的颜色，或者干脆用一个数组记录；用 DFS 实现时，递归函数多一个参数表示当前顶点应该染的颜色。两种写法殊途同归，下面是 BFS 版本：

from collections import deque

def is_bipartite(adj, n):
    color = [0] * n          # 0 未染色，1 和 2 是两种颜色
    for start in range(n):
        if color[start] != 0:
            continue
        color[start] = 1
        q = deque([start])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if color[v] == 0:
                    color[v] = 3 - color[u]   # 1 变 2，2 变 1
                    q.append(v)
                elif color[v] == color[u]:
                    return False              # 相邻同色：不是二分图
    return True

3 - color[u] 这个小技巧可以记一下：当颜色只有 1 和 2 时，3 - 1 = 2，3 - 2 = 1，正好完成颜色翻转，比写 if-else 更简洁。DFS 版本只是把队列换成了递归：

def dfs_color(adj, color, u, c):
    color[u] = c
    for v in adj[u]:
        if color[v] == 0:
            if not dfs_color(adj, color, v, 3 - c):
                return False
        elif color[v] == c:
            return False
    return True

def is_bipartite_dfs(adj, n):
    color = [0] * n
    for start in range(n):
        if color[start] == 0 and not dfs_color(adj, color, start, 1):
            return False
    return True

两个版本的复杂度都是 O(V+E)，因为每个顶点最多被染色一次，每条边最多被检查两次。空间上 BFS 需要队列，DFS 需要递归栈，都属于 O(V)。这里还有一个容易被忽略的细节：孤立顶点（没有任何边的顶点）不会造成任何冲突，染成哪种颜色都行，所以它不影响二分图判定；代码里外层循环会单独给它染色，但它既没有邻居要检查，也不会返回 False。

2.3 为什么奇环 = 不是二分图

理解了算法，接下来是更本质的问题：什么样的图不是二分图？ 答案非常优美——包含奇数长度环的图就不是二分图，反过来，没有奇环的图一定是二分图。用图论的话说：二分图等价于”无奇环图”。

先用直觉理解为什么奇环会出问题。想象一个三角形：A 和 B 相连，B 和 C 相连，C 和 A 相连。给 A 染红色，那么 B 必须染蓝色；C 和 B 相连，所以 C 必须染红色；可是 C 又和 A 相连，而 A 是红色、C 也是红色，两个相邻顶点撞色了。无论你从哪个顶点、用什么颜色起步，三角形的三个顶点会陷入”颜色循环”，最后一个顶点永远无法同时满足两条边的约束。环长是偶数时就不会这样：四边形的四个顶点可以染成红、蓝、红、蓝，绕一圈回来发现起点颜色正好衔接上，没有任何矛盾。

下面这张图直观地展示了这种差异。左边是一个三角形，染到第三个顶点时发现它既要和第一个顶点异色、又已经和第二个顶点同色相连，矛盾爆发；右边是一个四边形，红蓝交替一周，完美收场：

graph LR
    subgraph 奇环["奇环：冲突"]
        A1["A（红）"] --- B1["B（蓝）"]
        B1 --- C1["C（红）？"]
        C1 -. "撞色！" .- A1
    end
    subgraph 偶环["偶环：完美交替"]
        A2["A（红）"] --- B2["B（蓝）"]
        B2 --- C2["C（红）"]
        C2 --- D2["D（蓝）"]
        D2 --- A2
    end

为什么”有奇环”和”不是二分图”可以画等号？因为二分图要求每条边都跨组，而一个环要闭合，绕一圈回到起点时，跨越的次数必须能让”组别”回到原样。走一条边就换一次组，所以环上走一圈换组的次数等于环长；环长若是奇数，换了奇数次组，终点就会落在和起点不同的组里，可终点偏偏就是起点，这就产生了矛盾。环长若是偶数，换偶数次组，终点恰好回到原组，一切自洽。这个论证对任意长度的环都成立，所以结论是严格的：存在奇环 ⟺ 不是二分图。

还有一个漂亮的推论：任何树（以及森林）都一定是二分图，因为树里根本没有环，自然也没有奇环。很多题目会先给你一棵树，然后问能不能把顶点分成两组让所有边跨组，答案永远是”能”，随便按深度奇偶分层就行——树的深度奇偶分层本质上就是一种染色。这个观察在树形动态规划里经常用到，比如黑白染色计数问题。

值得一提的是，染色法还能顺手解决”最小分组”类问题：对于二分图，把颜色 1 的顶点放左边、颜色 2 的顶点放右边，就得到了一个合法的两组划分。不过要注意，二分图的划分通常不唯一（在连通分量内，如果整体交换两种颜色，得到的还是合法划分），算法给出的只是其中一种。

3 应用三：环检测

3.1 无向图：撞见已访问的邻居，且它不是父节点

第三个应用是环检测：判断一张图里有没有环。图里的环意味着从某个顶点出发，能沿着一条不重复经过顶点的路径走回自己。树是最典型的无环连通图，任何无向图只要加一条边就会产生环；而”能不能加这条边”恰恰是很多系统设计的核心问题，比如死锁检测、依赖分析、并查集的合并判断。

无向图的环检测有个非常漂亮的直觉：在 DFS 或 BFS 的过程中，如果遇到一个已经访问过的邻居，而它又不是”带你来到这里”的那个父节点，那么环就出现了。 为什么要把父节点排除掉？因为在无向图里，边 (u,v) 是双向的：当你从 u 走到 v 时，v 的邻居列表里躺着 u，而 u 已经被访问过了。如果不排除父节点，你会在每一条边（甚至没有环的树）上都误报”发现环”。所以判断条件必须严格写成：visited[v] 为真 且 v != parent[u]。

下面这张图演示了环被发现的那一刻。DFS 从 A 出发，沿 A → B → C 走到 D，然后 D 检查邻居 B，发现 B 已经访问过，而 B 并不是 D 的父节点 C——于是”D 通过边 (D,B) 回到了探索过的区域”，环 B → C → D → B 浮出水面：

graph TD
    A["A"] --- B["B"]
    B --- C["C"]
    C --- D["D"]
    D -. "发现环！" .- B

注意这里有个细节：在无向图里，当 D 检查邻居 B 时，算法判断出环；但如果检查顺序反过来，当 B 第一次访问 D 时，D 还未被访问，所以 B 只是正常地递归进入 D。也就是说，一条环会在它”闭合”的那条边上被检测到，至于是哪条边，取决于遍历顺序，但不管顺序如何，只要存在环，就总会有那么一刻撞见”已访问且非父节点”的邻居。

用 DFS 实现时，递归函数需要带一个参数 parent，告诉下一层”我是从哪个顶点来的”：

def has_cycle_undirected(adj, n):
    visited = [False] * n

    def dfs(u, parent):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                if dfs(v, u):
                    return True
            elif v != parent:
                return True
        return False

    for u in range(n):
        if not visited[u]:
            if dfs(u, -1):
                return True
    return False

外层循环依然不能省：图可能由多个分量组成，如果只从一个顶点出发，可能根本走不到另一个分量里的环。起始顶点的父节点传 -1 或者其他哨兵值，表示”我没有父节点”。BFS 版本同样可以检测无向图环：队列里不仅要存顶点，还要记录它的父节点（或者单独开一个 parent 数组）；当一个邻居已经访问过、又不是当前顶点的父节点时，就说明存在环。两种遍历的复杂度依然是 O(V+E)。

还有几个边界情况值得唠叨一下。自环（一条边两端是同一个顶点）当然算环：在 DFS 里，u 的邻居列表里有 u 自己，此时 visited[u] 为真，而 u != parent 通常成立，于是立刻检测到环，这符合直觉，因为自环确实构成一个长度为 1 的环。重边（两个顶点之间有多条平行边）也算环：从 u 到 v 走第一条边，再从 v 到 u 走第二条边，就走回原点了。处理时如果邻接表里存了重复边，环检测自然会报告有环，这在某些题目里需要你根据题意决定是否去重。另外，如果一个分量只有一个孤立顶点，它不可能形成环，DFS 会干净地返回。

3.2 有向图：DFS 三色标记（白、灰、黑）

有向图的环检测比无向图微妙得多，因为方向让”走回头路”有了截然不同的含义。无向图里，只要从 u 走到 v 之后还能从 v 走回 u，就是环；有向图里，你必须严格沿着箭头的方向走，才能构成环。A → B → A 是环，但 A → B 和 A → C 即使画在一起，也不算环，因为从 B 回不到 A。

于是只靠”已访问/未访问”两个状态就不够用了。标准做法是三色标记法：每个顶点有三种状态——白色表示从未访问过；灰色表示正在访问中，也就是当前 DFS 递归栈上的顶点（从入口顶点到当前顶点的这条探索路径）；黑色表示访问彻底完成，它的所有后代都已经处理完毕，不会再出现在任何递归路径上。判断环的规则变得异常简洁：在 DFS 过程中，如果遇到一个灰色邻居，就说明存在环。

为什么灰色邻居等于环？因为灰色意味着”这个顶点还躺在我当前这条探索路径上”。假如当前顶点是 u，u 想沿着边 (u,v) 访问 v，而 v 还是灰色的，说明 v 是 u 的某个祖先（或者就是 u 自己），于是从 v 出发有一条路径能到达 u，再加上边 (u,v)，v → … → u → v 就构成了一个环。反过来，如果遇到的是黑色邻居，那说明 v 已经彻底探索完毕，它和当前路径没有任何交集，边 (u,v) 只是”顺路搭了一根跨边”，不会形成环。

下面这张状态图展示了三色标记的流转过程：顶点从白色开始，进入递归栈变成灰色，递归返回后变成黑色；只有从灰色发现指向灰色的边（图中用红色虚线标出）才意味着环：

flowchart LR
    W["白：未访问"] --> G["灰：在递归栈上"]
    G --> B["黑：访问完成"]
    G -. "发现指向灰色的边 = 环" .-> G

代码实现时，用一个 color 数组，0 表示白、1 表示灰、2 表示黑：

def has_cycle_directed(adj, n):
    color = [0] * n        # 0 白，1 灰，2 黑

    def dfs(u):
        color[u] = 1
        for v in adj[u]:
            if color[v] == 0:
                if dfs(v):
                    return True
            elif color[v] == 1:
                return True
        color[u] = 2
        return False

    for u in range(n):
        if color[u] == 0 and dfs(u):
            return True
    return False

这段代码的节奏值得反复体会：进入顶点时先染灰，遍历所有邻居，如果邻居是白的就递归；如果邻居是灰的，直接报告有环；所有邻居处理完毕，才把自己染黑并返回。注意染色成黑色的时机：必须等所有邻居都处理完，而不是一进入函数就染黑，否则祖先信息就丢了。这个”灰 = 当前路径”的思路是很多高级算法（比如拓扑排序、Tarjan 求强连通分量）的公共底座，把它想透，后面会省力很多。

有些实现喜欢用 visited 加 on_stack（递归栈标记）两个布尔数组来代替三色数组，本质完全一样：visited 区分白/非白，on_stack 区分灰/黑。还有人用”时间戳”来模拟：记录每个顶点的进入时间和离开时间，若存在一条边从后进入的顶点指向先进入且还没离开的顶点，就有环。三种说法，同一个思想，面试时你只要能把”灰色代表正在递归路径上”讲清楚，怎么写都是加分项。

有向图的环检测还可以用 Kahn 算法（基于入度的拓扑排序）来做：不断删除入度为 0 的顶点，如果最后还有顶点删不掉，就说明存在环。这个角度和 DFS 三色标记互补：一个从”出边”看，一个从”入边”看。我们第 7 篇讲拓扑排序时会正式介绍 Kahn 算法，到时候你会发现环检测和拓扑排序根本就是一枚硬币的两面——有向图能拓扑排序，当且仅当它是无环的（DAG）。所以在第 7 篇之前，先把三色标记彻底吃透，那将是拓扑排序最顺滑的入口。

3.3 环检测的现实意义

环在依赖系统里几乎总是坏事。软件包管理器安装依赖时，如果包 A 依赖 B、B 依赖 C、C 又依赖 A，那么安装顺序就无法确定，因为每个包都”要求别人先装好自己”；编译器构建项目时，模块之间的循环依赖会导致无法确定编译顺序；数据库里的事务若形成等待环，就会死锁；课程表里如果 A 的前置课程是 B、B 的前置课程是 A，这门课永远无法安排。这些场景背后是同一个数学模型：有向无环图（DAG），而环检测就是判断”这张图还能不能干活”的第一道安检。

无向图的环检测也有自己的用武之地。最小生成树算法（Kruskal）在加入一条边之前要判断”会不会形成环”——虽然它用并查集实现更高效，但遍历视角的理解同样成立；计算机网络里检测网络拓扑是否有冗余回路，环意味着数据包可能无限转发；电路设计中检测回路可以避免信号死循环。“有环”和”无环”在无数系统里就是”可工作”和”不可工作”的分界线，这也是为什么环检测虽然代码只有十几行，却被视为图论最重要的基本功之一。

3.4 三色标记走查：状态是怎么一步步变的

纸上谈兵不如亲手走一遍。我们拿一张混合了”环”和”干净链”的有向图来做三色标记走查。图的构成是这样的：A → B → C → A 形成一个环，另外 D → E 是一条与环完全无关的链。从 A 开始 DFS，状态会怎么流转？

第一步：进入 A，A 从白色变成灰色，当前递归栈是 [A]。第二步：A 的邻居只有 B，B 还是白色，于是递归进入 B，B 变灰，递归栈变成 [A, B]。第三步：B 的邻居是 C，C 还是白色，递归进入 C，C 变灰，递归栈变成 [A, B, C]。第四步：C 的邻居是 A——注意，A 现在是灰色！这意味着 A 还在当前递归栈上，是 C 的祖先；从 A 出发沿递归路径可以到达 C（A → B → C），再加上边 C → A，就构成环 A → B → C → A。算法立刻报告”存在环”，无需继续探索。

再看 D → E 这条链。假设环被检测到之前，外层循环先处理了 D：D 变灰，进入 E，E 变灰；E 没有邻居，于是 E 变黑并返回，D 也变黑并返回。整个过程里，E 检查邻居时没有遇到任何灰色顶点，所以这里没有环。注意 D 和 E 与 A、B、C 之间没有任何边，所以它们不会互相干扰——这也是外层循环存在的意义：它保证每个互不相连的部分都各自完成一次完整的状态流转。

下面这张图把走查结束时的状态画了出来：A、B、C 三个顶点在发现环的那一刻都是灰色（它们共同躺在递归栈上），而 D、E 已经走完全程变成了黑色：

graph TD
    A["A（灰）"] --> B["B（灰）"]
    B --> C["C（灰）"]
    C --> A
    D["D（黑）"] --> E["E（黑）"]

这个走查还揭示了一个容易被忽略的点：发现环的时刻通常不是”遍历完整张图”之后，而是”撞见灰色邻居”的瞬间。 所以代码里 elif color[v] == 1: return True 这一行，往往在递归很深的地方就提前结束了整个算法，省下了大量不必要的探索。如果你在面试里被问到”环检测能提前终止吗”，答案就是：能，而且正是三色标记的天然优势。

走查完，你可能会想：如果图的规模特别大，递归会不会太深？确实会。有向图环检测的递归深度最坏等于顶点数，对于十万甚至百万级的顶点，语言默认的递归限制可能不够用。工程上常见对策有三种：把递归改成显式栈（自己维护”入栈/出栈”的灰色状态）；调大递归限制；或者改用 Kahn 算法（按入度剥离）来检测环，它不需要递归。三种方案各有取舍，但在理解层面，三色标记依然是所有方案共同的”思想源头”，先把思想吃透，实现方案随你挑。

4 应用四：洪水填充（Flood Fill）

4.1 油漆桶的直觉

第四个应用可能是你用得最多、却从没意识到它和图有关的算法：洪水填充（Flood Fill）。打开任何一款画图软件，选中油漆桶工具，点一下画面上的某个像素，那个像素所在的”同色连通区域”就会全部变成新颜色——这个看似魔法般的操作，背后就是一次图遍历。

把图像看成一个网格，每个像素是顶点，上下左右相邻且颜色相同的像素之间连一条边，那么”油漆桶点中的那一整片同色区域”恰好就是一个连通分量。洪水填充要做的就是：从起始像素出发，遍历整个连通分量，把每个顶点的颜色改成目标颜色。名字里的”洪水”非常传神——想象把一桶颜料倒在某个位置，颜料会顺着”颜色相同的通道”向四周蔓延，遇到不同颜色的”堤坝”就停下来。颜料蔓延的顺序可以是逐层扩散（BFS），也可以是见路就钻（DFS），最终覆盖的区域完全一样。

下面这张图展示了一次典型的洪水填充。左侧是填充前的 5×5 网格，灰色表示目标区域，白色表示”堤坝”（不同颜色的像素），起点用星号标出；右侧是填充后的结果，与起点四连通的所有灰色格子都变成了橙色，而被白色隔开的另一块灰色区域则安然无恙——因为颜料无法穿过颜色不同的像素：

graph TD
    subgraph 填充前
        A1["灰"] --- A2["灰"]
        A2 --- A3["灰"]
        A1 --- A4["灰"]
        A4 --- A5["灰"]
        A2 --- B2["白（堤坝）"]
        A3 --- B3["白（堤坝）"]
        B2 --- B3
        A4 --- C4["灰（被隔离）"]
    end
    subgraph 填充后
        D1["橙"] --- D2["橙"]
        D2 --- D3["橙"]
        D1 --- D4["橙"]
        D4 --- D5["橙"]
        D2 --- E2["白（堤坝）"]
        D3 --- E3["白（堤坝）"]
        E2 --- E3
        D4 --- F4["灰（被隔离）"]
    end

左图里有两块灰色区域，中间隔着一列白色像素。起点所在的灰色区域有五格，填充后全部变橙；右下角那格灰色虽然颜色和起点相同，但中间没有”同色通道”，所以它不在起点所在的连通分量里，颜色保持不变。这就是洪水填充和”把全图所有同色像素都改掉”的本质区别：它只改连通的那一片，而不是全图匹配。

4.2 DFS 实现：递归版与显式栈版

洪水填充的实现同样有两种主流姿势。DFS 版本最直白：从起点开始，如果当前格子越界、或者颜色不是目标旧颜色，就返回；否则把颜色改成新颜色，然后递归地填充上下左右四个邻居。这里的关键是先判断”是否属于区域”，再决定是否进入，顺序一颠倒，要么越界崩溃，要么把不该改的像素也改了。

def flood_fill(image, sr, sc, new_color):
    old_color = image[sr][sc]
    if old_color == new_color:
        return image          # 新旧颜色相同：直接返回，避免死循环
    rows, cols = len(image), len(image[0])

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if image[r][c] != old_color:
            return
        image[r][c] = new_color
        dfs(r - 1, c)
        dfs(r + 1, c)
        dfs(r, c - 1)
        dfs(r, c + 1)

    dfs(sr, sc)
    return image

注意到函数开头那句 if old_color == new_color: return image 了吗？这是一个非常容易被忽略、但极其重要的边界处理：如果新颜色和旧颜色相同，递归会在”颜色等于旧颜色 → 改成新颜色（还是同一个颜色）→ 继续递归”之间无限循环，把栈直接炸穿。很多经典面试题都会埋这个坑，主动处理它，是高手和初学者的分水岭。

递归版简洁优雅，但和岛屿数量一样，图像尺寸很大时递归深度可能超过语言限制。显式栈的迭代版可以绕开这个问题。用栈模拟 DFS 时，入栈时就要把颜色改掉，否则同一个格子可能被重复压入多次：

def flood_fill_iter(image, sr, sc, new_color):
    old_color = image[sr][sc]
    if old_color == new_color:
        return image
    rows, cols = len(image), len(image[0])
    stack = [(sr, sc)]
    image[sr][sc] = new_color
    while stack:
        r, c = stack.pop()
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old_color:
                image[nr][nc] = new_color
                stack.append((nr, nc))
    return image

迭代版的循环体里，“检查边界 → 检查颜色 → 立即染色 → 压栈”四步一气呵成。压栈顺序影响访问顺序（后进先出让最后压入的邻居先被访问），但最终填充的区域完全一样。如果你希望蔓延顺序是”一层一层往外扩”，把栈换成队列、把 pop() 换成 popleft() 就是 BFS 版本，代码其余部分几乎不动。

4.3 连通区域标注与更多应用

洪水填充的另一个常见变体是连通区域标注（Connected Component Labeling）：给图像中的每一块连通区域一个编号，第一块区域所有像素标记为 1，第二块标记为 2，依此类推。做法无非是把”涂成新颜色”换成”写上区域编号”，然后在外层循环里对每个未标注的像素发起一次填充，每发起一次，编号加一。你看，这又是连通分量统计的骨架，只是这次”颜色”换成了”编号”。下面这张图展示了一块 4×4 的图像，两块连通区域分别被标注为 1 和 2：

graph TD
    subgraph 区域1
        A["(0,0)=1"] --- B["(0,1)=1"]
        B --- C["(1,1)=1"]
        A --- D["(1,0)=1"]
    end
    subgraph 区域2
        E["(2,2)=2"] --- F["(2,3)=2"]
        E --- G["(3,2)=2"]
    end

连通区域标注在计算机视觉里是基础中的基础：OCR 系统用它在图像里找出每个文字字符的轮廓；医学影像处理用它把 CT 片上的肿瘤区域从背景中分离出来；工业质检用它数出传送带上的零件个数；地图软件用它把水域和陆地分块，便于矢量化和渲染。游戏里它也无处不在：扫雷游戏点开一个空格时，要把周围一大片空白区域一次性翻开，这就是一次以空格为起点、以数字格为边界条件的洪水填充；消消乐游戏消除同色方块后，判断哪些方块会掉落、哪些会重新匹配，本质上也在反复做区域分析；迷宫生成和寻路里，洪水填充甚至可以用来计算”每个格子离出口有多远”——从出口出发做 BFS，距离层层递增，走到哪一格就能立刻回答”这里距出口几步”。

洪水填充在时间复杂度上和前面的应用一致：每个像素最多被访问一次，每个像素检查四个邻居，总时间 O(像素数 × 4) = O(像素数)，空间 O(像素数)（递归栈或栈/队列）。对图像这种动辄百万像素的输入来说，线性时间意味着即使在手机上处理一张 1080p 的图片，也只需要几千万次基本操作，毫秒级完成——这也是它能在交互式画图软件里”跟手”的原因。

4.4 四个应用之间的关系

写到这里，你可以停下来回味一下：今天这四个应用，其实共享同一个骨架。连通分量统计是”外层循环 + 内层遍历 + 计数器”；二分图染色是”外层循环 + 内层遍历 + 染色数组”；环检测是”外层循环 + 内层遍历 + 父节点或三色状态”；洪水填充是”遍历连通分量 + 改写状态”。它们的差异不在遍历本身，而在于遍历时维护的额外信息和触发的判断条件。这个认识非常重要：学会 BFS/DFS 只是拿到了”怎么走”的引擎，今天的四个应用则是四种”边走边收集信息”的玩法，而图论里还有成百上千个算法，几乎都是在这台引擎上挂不同的仪表盘。

4.5 从洪水填充到 BFS 距离场

洪水填充的 BFS 版本有一个非常优雅的”副产品”：距离场。既然 BFS 是逐层扩散的，那么只要在入队时记录”我是第几层”，每个格子就会得到一个数字——它到起点的最短步数。这个数字有什么用？用处大了。

想象一座迷宫，出口在右下角。如果从出口出发做一次 BFS，每个格子都会得到一个”到出口的距离”：出口本身是 0，它四通八达的邻居是 1，再往外一圈是 2，依此类推。有了这张距离场，迷宫里任何一个位置的玩家都能立刻知道自己离出口还有几步——不需要每次重新寻路，查表即可。如果玩家还面临多个出口，从所有出口同时发起 BFS（多源 BFS），距离场记录的就是”到最近出口的距离”，这在地图导航、逃生路线规划里是标准操作。

下面这张 3×3 的迷宫展示了距离场的模样：右下角是出口，数字表示每个格子到出口的最短步数，黑色方块是墙：

graph LR
    subgraph 距离场["距离场（× 表示墙）"]
        A["4"] --- B["3"]
        B --- C["2"]
        C --- D["1"]
        D --- E["出口 0"]
        B --- F["×"]
        F --- G["2"]
        G --- E
        C --- H["×"]
        H --- I["1"]
        I --- E
    end

这张图里，从出口 0 出发，向上、向左、向下的格子分别得到 1；再往外推一圈得到 2；依此类推，左上角离出口最远，距离是 4。如果从左上角出发沿”数字递减”的方向走，每一步都能保证离出口更近一步，最终必然到达出口——这其实就是”梯度下降”最朴素的网格版，也是很多寻路算法（如势场法）的思想雏形。

距离场还能玩出更多花样：传染病模拟里，从感染源做 BFS，每个格子的数字就是”最早可能被感染的时间”，防疫部门可以根据它安排隔离和物资投放顺序；游戏里，从怪物巢穴做 BFS，得到”怪物到达每个格子需要多少回合”，玩家可以据此判断哪里安全、哪里危险；地图服务的”等时圈”（从某个地点出发，30 分钟、60 分钟分别能到达哪些区域）本质上也依赖这种逐层扩散的思想。你看，洪水填充只是”染色”，加一个层数计数器，就变成了”计时器”，这就是图遍历的魔力：同样的遍历，记录什么信息，就得到什么能力。

到这里，四个应用以及它们的延伸玩法就全部讲完了。从分量统计到染色判定，从环检测到洪水填充，再到 BFS 距离场，你手里已经握着一整套”遍历工具箱”。接下来的最后一节，我们把选择遍历方式的判断表、四应用速查表和自测题一并奉上。

5 应用综合：从算法到真实世界

四个算法单独看都很小，但它们组合起来，能回答现实世界里一大堆”看起来毫不相干”的问题。这一节我们放慢脚步，把镜头拉远，看看这些算法是怎么在真实系统里落地的。

5.1 社交网络：我的圈子到底有多大

先看社交网络。把每个用户当成顶点，把”互为好友”当成无向边，你立刻得到一张巨大的无向图。在这张图里，连通分量统计回答的是”谁和谁是一伙的”。你可能会觉得奇怪：现在的社交网络动辄几亿用户，为什么还要分析连通分量？因为在真实数据里，绝大多数社交网络并不是一个连通的整体，而是由”一个超级巨大的主分量 + 无数个小型圈子”构成的：主分量里几乎所有人都能通过”朋友的朋友”链到一起，而那些小型分量可能是同班同学群、家族群、某个小论坛的活跃用户，甚至是一群只有互相关注关系的僵尸账号。

下面这张示意图展示了一个小型社交网络被切成三个连通分量：左边是一群互相认识的同事，中间是一整个班级的同学，右边是一个孤零零的新注册用户（他还没有添加任何好友，但他依然是一个分量）：

graph LR
    subgraph 同事圈
        U1["小张"] --- U2["小李"]
        U1 --- U3["小王"]
        U2 --- U4["小赵"]
    end
    subgraph 班级圈
        U5["小明"] --- U6["小红"]
        U6 --- U7["小刚"]
        U7 --- U5
        U6 --- U8["小丽"]
    end
    subgraph 新用户
        U9["新注册用户"]
    end

产品经理拿到分量统计结果后能做什么？可以给”新注册用户”这种孤立分量推送好友推荐，因为从图的角度看，他们还没有被”吸”进任何社交圈；可以分析主分量的规模占比，评估平台的”连接密度”健康度；还可以结合后续的社区发现算法，找出圈子里真正有影响力的人。另外，两个人是否在同一个分量里本身就是一个高频查询：判断两个用户是否”间接认识”，直接查分量编号即可，比每次做一次 BFS 快得多——这就是”把分量编号预计算出来，把在线查询变成 O(1)“的典型套路，类并查集的思路，但今天我们用遍历同样能做到。

真实的社交网络数据还会出现一个有趣的现象，叫巨型连通分量：当用户之间的连接足够密集时，绝大多数活跃用户会被”朋友的朋友”链进同一个超大分量，剩下的用户则散落在数以百万计的小分量里。对这个巨型分量做一次 BFS，你甚至能得到”任意两个用户之间的平均最短距离”——著名的”六度分隔”实验就是这么做的：用遍历统计出所有用户对之间的距离，发现平均只有六步左右。这种”看似人人相隔万里，实则几步之遥”的结论，背后就是今天的分量统计和 BFS 层数信息在支撑。

5.2 电网与基础设施：断一条线，还剩几块

再看基础设施。把电网里的变电站当成顶点，把输电线路当成无向边，那么”整个电网是不是连通的”就等价于”连通分量数是不是 1”。电力调度员最关心的事情之一是鲁棒性：如果某一条线路因为故障被切断，电网会不会被劈成两半，导致部分地区停电？

这个问题可以直接用今天的工具来模拟：把要断开的边从图里删掉，再跑一次连通分量统计，看分量数量是否从 1 变成 2。如果变成 2，这条边就是所谓的桥（割边）——它一旦消失，图就分裂。判断一条边是不是桥，最简单的办法就是暴力枚举：对每条边删掉再数分量，复杂度 O(E×(V+E))，边数多时很慢；而图系列后面会讲到 Tarjan 算法，它能在一次 DFS 里找出所有桥，线性时间搞定。虽然高级算法更高效，但暴力方案的价值在于它永远不会错，可以作为验证高级算法正确性的”标尺”，这也是面试官喜欢追问的思维层次。

类似的场景还有：通信网络里基站之间的光纤断了，还有没有备用路径？城市供水管网里某段管道检修，哪些片区会变成孤岛？铁路网里某座枢纽站关闭，还有多少条线路能照常运营？这些问题都可以抽象成”删掉一些顶点或边之后，重新统计连通分量”，而每一次统计，我们都可以放心地使用今天学的 O(V+E) 遍历。值得强调的是，这类系统的特点是图规模大、但每个顶点的邻居数通常很小（变电站只连附近几条线），所以稀疏图的邻接表存储加上线性遍历，就是性价比最高的组合。

5.3 二分图：匹配与排班

二分图判定在现实里的应用，可以用两个字概括：匹配。假设有 n 个工人和 m 个岗位，每个工人能胜任其中若干岗位，现在要给尽可能多的工人安排工作，且每个岗位只能安排一个人——这就是经典的二分图最大匹配问题。为什么它一定是二分图？因为工人和岗位是两类实体，边只存在于”工人–岗位”之间，工人之间、岗位之间没有边。判断图是不是二分图，在这里几乎是免费的：这类关系图天然就是二分图，染色法跑一遍只是为了确认数据没有异常（比如不小心把两个工人连了一条边）。

排班问题是匹配的日常生活版。医院要安排医生值班：每个医生有自己不能值班的日期，每天至少要有一名医生在岗。把医生放左边、日期放右边，能值班就连边，那么”是否存在一个合法排班方案，让每个日期都有医生”就是”能否找到一个覆盖所有日期的匹配”。如果某天只有一名医生能值班，而他又被安排在了别处，算法就必须重新调配——匈牙利算法和网络流就是在二分图上做这种”全局调配”的高手，它们都以”图是二分图”为前提。你可能会问：判断二分图本身有什么实际意义？因为很多高效算法只对二分图有效，在动手跑匹配算法之前先花 O(V+E) 时间做一次染色检查，可以避免在错误的数据上白跑一遍。另外，如果一张图被染色判定为二分图，两个颜色类别的顶点数本身就给出了匹配大小的上界，这对剪枝和估算很有用。

下面这张图是医院排班问题的简化版：左边三位医生，右边四天，医生与可值班的日期之间连边。你能一眼看出它是一张二分图，因为所有边都横跨左右两组：

graph LR
    subgraph 医生
        D1["医生甲"]
        D2["医生乙"]
        D3["医生丙"]
    end
    subgraph 日期
        X1["周一"]
        X2["周二"]
        X3["周三"]
        X4["周四"]
    end
    D1 --- X1
    D1 --- X2
    D2 --- X2
    D2 --- X3
    D3 --- X3
    D3 --- X4

第 15 篇我们会正式展开二分图匹配，包括最大匹配、完美匹配和带权匹配，那里你会看到染色判定留下的伏笔如何被逐一兑现。

5.4 依赖系统：环就是事故现场

最后回到依赖系统。软件世界里，环检测几乎是”安装依赖”这个动作的前置安检：npm、pip、Maven 这些包管理器在解析依赖树时，必须保证依赖关系不构成环，否则无法确定安装顺序。构建系统（Make、Gradle、Bazel）把任务和任务之间的依赖画成有向图，如果图里有环，构建就会陷入”先有鸡还是先有蛋”的死局，所以构建前必须先做一次环检测，发现环就报错并指出环上的任务。

下面这张图是一个真实的”环事故现场”：模块 A 依赖 B，B 依赖 C，C 又依赖 A，三者的依赖关系首尾相接；而 D 和 E 的依赖关系是干净的链式结构，可以正常构建：

graph LR
    A["模块 A"] --> B["模块 B"]
    B --> C["模块 C"]
    C --> A
    D["模块 D"] --> E["模块 E"]

有向图环检测在这里还有一个进阶用途：找出环上的所有顶点。当三色标记发现”灰色邻居”时，我们可以顺着递归栈回溯，把从那个灰色顶点到当前顶点的整条路径输出，这就是一条具体的环。包管理器拿到这条环，就能在报错信息里精确告诉开发者”你的 A、B、C 三个包互相依赖”，而不是含糊地说一句”存在循环依赖”。

更妙的是，环检测和拓扑排序是一对搭档：拓扑排序给 DAG 里的任务排出一个合法的执行顺序（先做所有前置任务，再做后继任务），而环检测负责”体检”——只有无环图才有资格被排序。第 7 篇我们会学到 Kahn 算法和基于 DFS 的拓扑排序，到那时你会发现，DFS 拓扑排序和三色标记环检测几乎是同一段代码：染黑顶点时按顺序记录下来，逆序输出就是拓扑序。所以今天的每一行代码，都在为下一篇铺路。

5.5 全流程走查：一张图跑完四个算法

抽象的应用讲多了，容易让人觉得每个算法都是孤岛。这一小节我们拿一张具体的图，把今天四个应用从头到尾各跑一遍，看看它们是怎么在同一张图上各司其职的。就用下面这张 7 个顶点的无向图，顶点 A 到 F 之间有一个三角形和一条尾巴，顶点 G 是孤立的：

graph TD
    A["A"] --- B["B"]
    B --- C["C"]
    C --- A
    C --- D["D"]
    D --- E["E"]
    E --- F["F"]
    G["G"]

第一步：统计连通分量。 外层循环从 A 开始，发起一次 DFS。A 的邻居 B、C 陆续被访问，C 又带出 D，D 带出 E，E 带出 F，所以一次遍历就把 A、B、C、D、E、F 六个顶点全部标记。外层循环继续扫描，发现 G 还没有被访问，于是发起第二次 DFS，G 没有邻居，遍历立刻结束。计数器最终等于 2：图里有 1 个大分量和 1 个孤立顶点分量。这个结果告诉我们：如果这是社交网络，A 到 F 之间所有人都互相”间接认识”，而 G 和谁都没有联系，需要额外运营。

第二步：判定二分图。 从 A 开始染色：A 染成颜色 1。B 是 A 的邻居，染成颜色 2；C 是 B 的邻居，染成颜色 1。这时检查边 C—A：C 的颜色是 1，A 的颜色也是 1，两个相邻顶点同色，冲突爆发！算法立刻返回 False，整张图不是二分图。这个冲突不是偶然的：三角形 A-B-C 就是一条奇数环，根据”奇环 = 不是二分图”的定理，只要图里存在这个三角形，染色就必然失败。有趣的是，如果把 A—C 这条边删掉，剩下的 A-B-C-D-E-F 是一条纯路径，可以轻松交替染成 1、2、1、2、1、2，整张图就变成二分图了。可见一条边可以彻底改变一张图的性质。

第三步：检测环。 再从 A 出发做 DFS，这次带上父节点信息。假设访问顺序是 A → B → C → D → E → F，一路走到 F 发现没有未访问邻居，于是回溯到 E、D、C。在 C 检查邻居时，发现 A 已经访问过了；A 是 C 的父节点吗？不是——C 的父节点是 B，所以条件”已访问且非父节点”成立，环检测报告有环。这条环就是 A-B-C-A，也就是第二步里那个惹祸的三角形。如果你用 BFS 做，结果也一样：当某个顶点发现一个”已访问且不是自己父节点”的邻居时，环就现身了。检测到环之后，如果这是一张任务依赖图，系统就可以立刻报警，拒绝执行；如果这是一张电路图，说明信号可能在这里形成回路。

第四步：洪水填充。 洪水填充通常作用在网格上，和上面这张抽象图不是同一类输入，但它和前三步共享同一个灵魂：从起点出发遍历一个连通区域。我们换成一张 3×3 的像素图来看：灰色区域从左上角延伸到中间，右下角还有一块被白色隔开的灰色。用油漆桶点中间的灰色格子，递归会向上下左右蔓延，把同一块灰色区域全部染成橙色；右下角那块灰色因为中间隔着白色像素，颜色保持不变。换句话说，洪水填充就是”以颜色为边”的连通分量遍历，只不过它把”统计数量”换成了”改写状态”。

graph LR
    subgraph 走查网格["走查网格（3×3）"]
        P1["灰"] --- P2["灰"]
        P2 --- P3["灰"]
        P1 --- P4["灰"]
        P4 --- P5["灰"]
        P2 --- W1["白"]
        P3 --- W2["白"]
        P5 --- W3["白"]
        W3 --- W2
        P5 --- P6["灰（被隔离）"]
    end

走查完毕。你会发现，四个应用在同一个数据模型上运行，只是每次”遍历时多看一眼”的东西不同：分量统计数的是遍历次数，染色查的是邻居颜色，环检测盯的是父节点和访问状态，洪水填充改的是顶点颜色。这种”同一引擎、不同仪表”的心智模型，就是今天这篇最重要的收获。

5.6 高频疑问

最后，把读者问得最多的四个问题集中回答一遍。问题一：连通分量统计里的 visited 数组能省吗？ 不能。没有 visited，遍历会在环里无限循环；即使只处理树，重复访问也会让每个子树被反复计算，复杂度爆炸。visited 是”每个顶点只处理一次”的保证，也是所有线性时间图算法的基石。问题二：有向图能不能用”visited + 父节点”的方法检测环？ 不能。有向图里，即使遇到已访问的非父节点邻居，也可能只是”从别的分支搭过来的一条边”，不构成环；必须区分”还在递归路径上”（灰色）和”已彻底完成”（黑色），所以三色标记是必须的。问题三：洪水填充用 BFS 还是 DFS 好？ 功能上等价，选型看两点：怕不怕递归深度（大图、长条区域选 BFS 或显式栈），以及是否需要”逐层”效果（需要距离信息选 BFS）。画图软件里实现油漆桶，很多工程实现反而偏爱显式栈，因为它在栈溢出风险和缓存局部性之间取得了平衡。问题四：稀疏图和稠密图会影响今天的算法吗？ 复杂度公式 O(V+E) 本身就包含 E，所以两种图都能处理；真正的差别在存储方式：稀疏图用邻接表省空间，稠密图用邻接矩阵访问快。如果你还在纠结这个问题，建议回到第 3 篇（图的存储）复习一遍。

6 小结：BFS 还是 DFS？一张判断表

学完四个应用，你可能会问一个非常实际的问题：同一个问题，BFS 和 DFS 都能做，那我到底该选哪个？ 今天的每个应用我们都同时给了两种实现，这在理论上没有错——分量统计、二分图染色、无向图环检测、洪水填充，BFS 和 DFS 都能给出正确结果。但工程上，两者的性格差异会带来实实在在的区别，选对了能让代码更短、空间更省、行为更符合直觉。

6.1 BFS 的主场：层级与最短

BFS 按层推进，天然自带”距离”信息。只要图是无权的（每条边代价相同），BFS 第一次到达某个顶点时，走过的路径就是最短路径；BFS 同时还会告诉你”这个顶点在第几层”，这在很多问题里就是答案本身。所以，只要题目涉及”最短步数、最少次数、最少操作、最近距离”，优先考虑 BFS。经典例子包括：迷宫里的最短路径、单词接龙的最少转换次数、打开转盘锁的最少拨动次数、社交网络里两个人的”六度分隔”距离。

BFS 还擅长”目标离起点不远”的场景。如果问题只问”从起点出发，几步以内能不能到达目标”，BFS 可以逐层扩展，找到目标就立即停止，不需要把整张图走完；DFS 则会一头扎进某个分支的最深处，可能把远在天边的死路全部探完才发现目标其实近在咫尺。另外，BFS 的空间开销和”当前层的宽度”成正比，对于”宽度小、深度大”的图（比如链状图），BFS 队列里最多只有一两个顶点，空间非常省；但对于”宽度爆炸”的图（比如每个顶点有 10 个邻居的树），BFS 队列会快速膨胀。

6.2 DFS 的主场：连通与回溯

DFS 的主场是连通性探索、路径枚举和状态回溯。它不需要队列，递归时用系统栈，空间上通常只和”当前探索深度”成正比；对于”深度小、宽度大”的图，DFS 的空间往往比 BFS 省得多。而且 DFS 的递归结构天然支持”沿着一条路径走到头”的场景：判断图中两个顶点是否连通、在迷宫里找一条可行路径（不要求最短）、枚举所有可能的路线、回溯法解数独和八皇后，这些任务用 DFS 写起来最自然。

DFS 在今天的四个应用里还有一个隐藏优势：环检测和拓扑排序的衔接。有向图环检测的三色标记、找环上的顶点、DFS 拓扑排序，全部建立在”递归栈”这个结构上；如果强行用 BFS 实现三色思想，就要自己维护一个栈来模拟回溯，代码反而更绕。所以当你预感到题目和”依赖、顺序、环、路径”有关时，DFS 往往更顺手。

下面这张流程图总结了选型决策：看到题目先问”是不是无权图的最短问题”，是就上 BFS；再问”是不是连通性、环、路径枚举、回溯”，是就上 DFS；两者都行时，看空间和实现难度：

flowchart TD
    Q1{"问题需要最短步数/最少次数？"} -- "是" --> BFS["BFS：逐层扩散，首次到达即最短"]
    Q1 -- "否" --> Q2{"问题涉及连通性、环、路径、回溯？"}
    Q2 -- "是" --> DFS["DFS：递归天然贴合"]
    Q2 -- "否" --> Q3{"图很深还是很宽？"}
    Q3 -- "深度大" --> DFS
    Q3 -- "宽度大" --> BFS

再把 BFS 和 DFS 的关键差异整理成一张表，方便随时查阅：

维度	BFS	DFS
数据结构	队列	递归栈 / 显式栈
遍历顺序	按层推进	一路走到黑再回头
能否求无权图最短路径	能，首次到达即最短	不能直接保证
空间占用	与最大层宽度成正比	与最大探索深度成正比
连通分量 / 二分图 / 洪水填充	都能做	都能做
无向图环检测	能做，需要记录父节点	能做，需要记录父节点
有向图环检测	不自然（需要模拟递归栈）	三色标记，天然贴合
拓扑排序	Kahn 算法（按入度）	DFS 逆序输出
典型题目	最短路径、层序、开锁	岛屿、迷宫、回溯、环检测

6.3 四个常见误区

趁热打铁，把初学者最容易踩的四个坑集中扫一遍。第一个坑：visited 标记时机不对。 在 BFS 里，顶点入队时就要标记为已访问，而不是出队时才标记，否则同一个顶点可能被多个邻居重复入队，队列膨胀、效率下降，严重时还会把”首次到达即最短”的性质破坏掉。在 DFS 里，标记时机同样要小心：如果递归进入后再标记，可能一个顶点在被标记前就被另一个邻居重复调用，造成指数级冗余。第二个坑：无向图环检测忘了排除父节点。 每一条无向边都会让子顶点”看见”已访问的父顶点，不排除它就会把树误判成环，这是无向图环检测错误率最高的原因。第三个坑：忽略了多分量。 图可能不连通，外层循环必须覆盖所有顶点；只从起点做一次遍历，会漏掉其他分量里的环和未染色顶点。第四个坑：洪水填充忘记处理新旧颜色相同。 新旧颜色一样时如果不提前返回，递归将无限循环，直到栈溢出；面试题里这个坑几乎必考。

7 四应用速查表

最后，把今天的四个应用浓缩成一张速查表，贴在文章末尾，方便以后回来复习：

应用	核心思路	关键判断	典型代码量	复杂度
连通分量统计	外层循环，遇到未访问顶点就发起一次遍历	每次新遍历 = 一个新分量	约 15 行	O(V+E)
二分图判定	遍历时交替染 1/2	相邻顶点同色即冲突	约 20 行	O(V+E)
环检测（无向图）	遇到已访问邻居且不是父节点	有此类邻居即有环	约 20 行	O(V+E)
环检测（有向图）	DFS 三色标记	遇到灰色邻居即有环	约 20 行	O(V+E)
洪水填充	从起点遍历同色连通区域并改写	边界 + 颜色匹配	约 20 行	O(V+E)

这张表有一个共同点：所有应用都是 O(V+E)，都在”遍历引擎”上挂一层额外逻辑。 记住这个模式，比背下任何一段代码都重要。以后遇到新问题，先问自己三句话：这是一个图问题吗？图的顶点和边分别是什么？遍历时我需要收集什么信息？把这三句话想清楚，答案往往自己就浮出来了。

顺便提一句，今天这四个应用在面试题里几乎都是”换皮”出现：最大岛屿面积是分量统计加一个面积计数器；岛屿周长是统计”陆地与海相邻的边数”；被围绕的区域是先从边界做洪水填充标记安全区，再把剩下被包围的格子翻转；课程表是典型的有向图环检测；判断二分图则常常直接以”把一群人分成两组，互相认识的人不能同组”的包装出现。看到这些题目时，先别急着背题解，回到今天的框架里问一句”顶点是谁、边是谁、遍历时要记录什么”，你会发现它们全是同一套拳法。

8 自测题

附加挑战题（学有余力再想）：给一张无向图，要求输出所有连通分量的”大小”（顶点数量），并按从大到小排序。这道题没有新算法，只是把今天两个知识点组合起来：DFS 每访问一个顶点就把计数器加一，一次遍历结束就得到一个分量的大小，收集所有大小后排序即可。真正的难点在于实现细节——计数器要作为返回值或共享变量正确传递，递归返回时不能把已经统计过的顶点重复计入。你可以试试：把计数器写在递归函数外面，每次发起遍历前清零，遍历结束后把值存入列表，最后排序输出。这道题练的不是智商，而是”在正确的位置更新状态”的代码手感，而这恰恰是今天所有应用共同的关键。

9 综合实战：把四个应用拼起来

题做完了，最后再看一个把今天所学串起来的综合案例，体会”一个系统里同时出现四个应用”是什么感觉。

假设你在开发一款像素风地图编辑器。用户先画出一张由不同颜色方块组成的地图，然后系统需要自动完成四件事：第一，统计地图上有几片独立的陆地（连通分量统计）；第二，把”可通行区域”和”障碍区域”分别识别出来，供游戏寻路模块使用（洪水填充 + 区域标注）；第三，检查地图上有没有”怪物巡逻环”——如果巡逻路线形成环，怪物就会永远绕圈不回头（无向图环检测）；第四，把玩家与资源点的关系建成一张图，判断能不能把玩家和资源点两两配对（二分图判定，为后续匹配做准备）。

这四个任务看似彼此独立，但底层都是同一套遍历引擎。更妙的是，它们的数据是共享的：连通分量统计跑一遍，每个格子就拥有了”分量编号”；洪水填充跑一遍，每个格子又拥有了”区域编号”；环检测跑一遍，地图的”巡逻网络”是否安全就一清二楚了。你不需要为每个任务重新建立一套图结构，只需要在遍历时多维护一个数组。下图是这个编辑器内部的数据流：

flowchart LR
    原始地图["像素地图"] --> 网格建模["网格 → 图：格子是顶点，相邻是边"]
    网格建模 --> 分量统计["分量统计：岛有几片"]
    网格建模 --> 洪水填充["洪水填充：区域标注"]
    网格建模 --> 环检测["环检测：巡逻路线安全吗"]
    网格建模 --> 染色判定["染色判定：能配对吗"]

这个案例告诉我们：算法从来不是孤立的知识点，它们是同一台机器上互相咬合的齿轮。 今天学的四个应用，加上第 4、5 篇的两种遍历，已经足够你解决一大批真实世界的图问题；而它们之上，还叠着拓扑排序、最短路径、最小生成树、最大流、匹配等一座座更高的山峰。

10 下一篇预告

下一站，我们进入图系列一个承上启下的主题：《图系列第 7 篇：拓扑排序与 DAG》。

拓扑排序回答的问题非常接地气：给定一堆任务和它们之间的先后依赖关系，能不能排出一种合法的执行顺序？课程表要怎么安排才能让每门课的前置课都先修完？编译器的源文件要怎么安排编译顺序才能让每个模块的依赖先就绪？包管理器安装依赖时按什么顺序逐个安装？这些问题的答案，都藏在”有向无环图”里。

在第 7 篇里，你会看到两个老朋友以新身份出场：今天学的三色标记环检测，会变成 DFS 拓扑排序的左膀右臂——染黑的顺序逆过来，就是拓扑序；而 BFS 的层序思想会孕育出 Kahn 算法——不断删除入度为 0 的顶点，像剥洋葱一样把 DAG 一层层剥开。你还会学到：为什么拓扑排序只对 DAG 有效，环检测如何和拓扑排序无缝配合，以及拓扑排序在真实系统里那些让人拍案叫绝的应用。

今天就到这里。记得打开可视化实验室亲手拖几张图试试：给同一个图分别跑 BFS 和 DFS，观察连通分量；给二分图和非二分图各染一次色，看看冲突发生在哪条边；再画一个带环的有向图，看三色标记在哪里喊停。纸上得来终觉浅，绝知此事要躬行——我们第 7 篇见！

写在最后

回头看看今天走过的路：我们从”遍历”这个最基础的动作出发，一路延伸出连通分量统计、二分图染色、环检测、洪水填充四个经典应用，又从应用走向社交网络、电网、排班、依赖系统这些真实世界，最后用一张图把四个算法完整走查了一遍。你会发现，真正难的不是记住 BFS 用队列、DFS 用栈，而是把问题翻译成图：顶点是什么，边是什么，遍历时该收集什么信息。一旦翻译完成，算法本身往往水到渠成。

这也是图系列一贯的写作哲学：先建立直觉，再落代码，再回看本质。第 4、5 篇给了你两把钥匙——BFS 和 DFS；今天这篇让你看到这两把钥匙能打开的四扇门；而第 7 篇开始，我们会走进拓扑排序、最短路径、最小生成树、强连通分量、匹配与网络流这些更深的大殿。每一篇都在复用前面打下的地基，所以如果你今天有任何一处还觉得模糊，别急着往下走，回头把对应的段落再读一遍，或者去可视化实验室拖一张图亲手验证。

算法的学习没有捷径，但有一条明确的路：看得懂 → 写得对 → 讲得清 → 用得出。今天这篇的目标是帮你走完前两步，顺便给第三步递上梯子。如果你还想检验自己是否真的掌握了，不妨合上文章，凭记忆在白纸上画出四张图：一张多分量的无向图、一张带奇环的图、一张带环的有向图、一张等待填充的网格，然后分别写出对应的判断流程和核心代码，再对照文章检查。能独立画出来、讲明白，才算真正装进了自己的知识体系。接下来，就让第 7 篇的拓扑排序来检验你的成色吧。我们下一篇见！