12.4　连通分量、环检测与二分图

学习目标：学完本节，你能

  • 用 DFS/BFS 数出图里有几个连通分量；
  • 说清无向图和有向图"环检测"为什么方法不同；
  • 用染色法判断二分图，并说出它和"奇环"的关系；
  • 看出这三个问题其实是同一个骨架上的不同挂载。

先修：12.2（DFS）、12.3（BFS）。 固定术语：连通分量、环检测、三色标记、二分图。 环境与版本：.NET 8 / C# 12。 预计阅读：30 分钟。

一、总览：三个"加一点东西"的问题

这三个问题都不需要新的算法 —— 它们都是在 DFS/BFS 的骨架上加一点点东西。

问题 基础算法 加什么
连通分量 DFS 外层循环遍历所有顶点
无向图环检测 DFS 传递 parent 参数
有向图环检测 DFS 三色标记（区分灰色/黑色）
二分图判定 BFS 给顶点染色，检查相邻是否同色

这就是图算法的特点：遍历是骨架，各种问题只是往骨架上挂信息。

你要学的不是"十个独立的算法"，而是"一个骨架 + 十种挂载方式"。

二、连通分量

问题：图里有几个"互不相通的部分"？

以 9 个顶点的图为例：

    分量 1: 0 —— 1 —— 2（三角形）
    分量 2: 3 —— 4
    分量 3: 5（孤立顶点）
    分量 4: 6 —— 7 —— 8（一条链）

算法很简单：

static List<List<int>> FindComponents(Graph g)
{
    var visited = new bool[g.VertexCount];
    var components = new List<List<int>>();

    for (int v = 0; v < g.VertexCount; v++)
    {
        if (visited[v]) continue;              // 已经属于某个分量了

        var component = new List<int>();
        var stack = new Stack<int>();
        stack.Push(v);

        while (stack.Count > 0)                // 一次 DFS，覆盖一个分量
        {
            int cur = stack.Pop();
            if (visited[cur]) continue;
            visited[cur] = true;
            component.Add(cur);

            foreach (int next in g.Neighbors(cur))
                if (!visited[next]) stack.Push(next);
        }

        components.Add(component);
    }
    return components;
}

实测：

  找到了 4 个连通分量：
    分量 1: {0, 1, 2}
    分量 2: {3, 4}
    分量 3: {5}
    分量 4: {6, 7, 8}

核心洞察：

对每个"还没访问过的"顶点启动一次 DFS，一次 DFS 能覆盖到的所有顶点就是同一个分量。

DFS 的次数 = 连通分量的个数。

这个"外层再套一个循环"的模式很重要 —— 12.2 节的 DFS 是从一个指定起点出发的，所以只能保证覆盖"起点所在的那个分量"。

要覆盖全图，必须遍历所有顶点，对没访问过的启动新的遍历。

这个模式在别的地方也会用到：

  • 数"图里有几块"（社交网络的"朋友圈"数量）
  • 判断图是否连通（分量数 == 1 就是连通的）
  • 12.1 节提到的"并查集" 能更高效地解决同一类问题（但超出本书范围）

三、无向图环检测

问题：图里有没有环？

最直接的思路：DFS 时记住"我是从哪来的"，如果遇到一个已经访问过、又不是我来的地方的邻居，那就是环。

static bool HasCycleUndirected(Graph g)
{
    var visited = new bool[g.VertexCount];

    bool Dfs(int v, int parent)
    {
        visited[v] = true;
        foreach (int next in g.Neighbors(v))
        {
            if (!visited[next])
            {
                if (Dfs(next, v)) return true;
            }
            else if (next != parent)
            {
                return true;      // ★ 遇到「访问过且不是父节点」的邻居 -> 有环
            }
        }
        return false;
    }

    for (int v = 0; v < g.VertexCount; v++)
        if (!visited[v] && Dfs(v, -1)) return true;

    return false;
}

实测：

  情形 A（有三角形 0-1-2）：
        0 —— 1
         \  /
          2 —— 3 —— 4
    有环吗？True

  情形 B（一条链，无环）：
        0 —— 1 —— 2 —— 3 —— 4
    有环吗？False

为什么需要 parent？

因为无向图的边是双向的。

  从 0 走到 1 时，1 的邻居里【一定有 0】—— 那是你刚来的地方。
  如果你不排除它，就会误以为"遇到了已访问的邻居"，把正常的来路当成环。

实测追踪（三角形 0-1-2-0）：

  从 0 出发 -> 走到 1 -> 再走到 2
  在 2 的位置，邻居有：
    1（parent，跳过）
    0（已访问，【不是】 parent）-> 发现环 ✓

parent 的作用就是"排除来路" —— 无向图里唯一的"假环"就是这条来路。

四、有向图环检测：三色标记

有向图的环检测不能用上面的方法，因为：

  有向图里 A -> B 不代表 B -> A ——
  所以「遇到已访问的邻居」可能是【正常的交叉】，而不是环。

举个例子：

      0 -> 1 -> 2 -> 3 -> 4
       \_______________/
  （0 同时还有一条边直接到 2）

从 0 走到 1、再到 2 时，2 已经被"访问过"了 —— 但这显然不是环。

所以需要区分"两种已访问"：

颜色 含义 遇到它意味着
白色（0） 没访问过 正常，继续探索
灰色（1） 正在访问 —— 在当前 DFS 路径上 有环！
黑色（2） 访问完了 —— 所有后代都探索过了 交叉边，不是环 
static bool HasCycleDirected(DiGraph g)
{
    var color = new int[g.VertexCount];        // 默认全是 0（白色）

    bool Dfs(int v)
    {
        color[v] = 1;                          // 标记为灰色（进入）
        foreach (int next in g.Neighbors(v))
        {
            if (color[next] == 1) return true;          // ★ 遇到灰色 -> 有环！
            if (color[next] == 0 && Dfs(next)) return true;
        }
        color[v] = 2;                          // 标记为黑色（离开）
        return false;
    }

    for (int v = 0; v < g.VertexCount; v++)
        if (color[v] == 0 && Dfs(v)) return true;

    return false;
}

实测：

  情形 A（任务依赖，无环）：
        0 -> 1 -> 2 -> 3 -> 4
         \______/
    有环吗？False

  情形 B（有环）：
        0 -> 1 -> 2 -> 3
              ^_________|
    有环吗？True

三色标记的核心洞察：

"灰色的顶点" = "当前 DFS 路径上的顶点"。

如果从某个顶点出发，能走回到路径上的某个顶点 —— 那就是一个环。

而黑色顶点是"已经探索完毕、退出了路径"的 —— 走到那里只是"抄了个近道"，不构成环。

这个"灰 vs 黑"的区分，就是有向图环检测的全部精髓。

这个概念在 13.1 节的拓扑排序里还会出现 —— 有向图能拓扑排序的充要条件就是"没有环"。

五、二分图判定

问题：能不能把顶点分成两组，使得每条边的两端都在不同的组？

等价的说法：能不能用两种颜色给所有顶点染色，且相邻顶点颜色不同？

算法就是一次染色版的 BFS：

static bool IsBipartite(Graph g, out int[] color)
{
    color = new int[g.VertexCount];
    Array.Fill(color, -1);                     // -1 = 还没染色

    for (int start = 0; start < g.VertexCount; start++)
    {
        if (color[start] != -1) continue;

        color[start] = 0;
        var queue = new Queue<int>();
        queue.Enqueue(start);

        while (queue.Count > 0)
        {
            int v = queue.Dequeue();
            foreach (int next in g.Neighbors(v))
            {
                if (color[next] == -1)
                {
                    color[next] = 1 - color[v];       // ★ 染成相反的颜色
                    queue.Enqueue(next);
                }
                else if (color[next] == color[v])
                {
                    return false;                     // ★ 相邻同色 -> 不是二分图
                }
            }
        }
    }
    return true;
}

实测（三种图形）：

  情形 A（一条链 0-1-2-3）：
    是二分图吗？True
    两组: 红组 = {0,2}, 蓝组 = {1,3}

  情形 B（三角形 0-1-2-0）：
    是二分图吗？False

  情形 C（正方形 0-1-2-3-0，偶数环）：
    是二分图吗？True
    两组: {0,2} 和 {1,3}

规律：二分图 ⟺ 不含奇数长度的环

图形 环的长度 是二分图？
链 无环 ✅ 是
三角形 3（奇） ❌ 不是
正方形 4（偶） ✅ 是
五边形 5（奇） ❌ 不是

为什么三角形不行？

3 个顶点两两相连（完全图 $K_3$），无论怎么分成两组，总有两个顶点落在同一组 —— 而它们之间有边，违反了"同组内不能有边"。

推广：任何奇数长度的环，都不可能用两种颜色交替染完 —— 因为绕一圈回来，颜色会和自己冲突。

为什么偶数环可以？

红蓝交替染一圈，正好回到起点时颜色还是对的 ✓

二分图的实际应用：

场景 两组是什么
任务分配 "做任务的人" vs "被做的任务"
排班 "白班" vs "夜班"（不能连排）
代码冲突检测 相互冲突的两个模块
社交网络的"敌对关系" 能否把用户分成两个阵营，使每个敌对关系都跨阵营

典型问题："能不能把一组人分成两队，使得每一对互相讨厌的人都在不同的队？" —— 这就是二分图判定。

六、统一视角

把四个问题放在一起看：

  问题                 | 基础算法           | 额外加什么
  --------------------------------------------------------------------------
  连通分量                 | DFS              | 外层循环遍历所有顶点
  无向图环检测            | DFS              | 传递 parent 参数
  有向图环检测            | DFS              | 三色标记（区分灰色/黑色）
  二分图判定               | BFS              | 给顶点染色，检查相邻是否同色

共同点：

都是在 DFS/BFS 的骨架上加一点点东西 —— 要么多传一个参数（parent），要么多维护一个数组（color）。

这就是图算法的特点：遍历是骨架，各种问题只是往骨架上挂信息。

这个视角为什么重要？

因为它把"要记的算法数量"从"十几个"降到了"两个"（DFS 和 BFS）+ "若干种挂载方式"。

遇到新的图问题时，不要急着想"这是什么算法" ——

先问："这是不是某种遍历？我需要额外记录什么信息？"

本章后面学的（拓扑排序、最短路）也遵循同一个模式：

  • 拓扑排序（13.1）：DFS 的后序 + 记录完成顺序
  • Dijkstra（13.3）：BFS 换成优先队列 + 记录距离

七、练习

练习 12.4.1（连通分量） 一个图有 8 个顶点，边是：(0,1), (1,2), (3,4), (5,6), (6,7)。 (a) 有几个连通分量？分别是什么？ (b) 如果加上边 (2,3)，变成几个分量？ (c) 再加 (7,0) 呢？

练习 12.4.2（环检测） 判断下面的图有没有环，并说明是哪一条：

  0 -> 1 -> 2 -> 3
       ^         |
       |_________|

(a) 用本节的三色标记法推演一遍。 (b) 如果把最后一条边 3 -> 1 改成 3 -> 4（4 是新顶点），还有环吗？

练习 12.4.3（判断） 判断对错并说明理由： (a) 无向图环检测和有向图环检测可以用同一个算法。 (b) 树一定有 $n-1$ 条边，所以"边数 = 顶点数 - 1"的图一定是树。 (c) 二分图的判定可以用 DFS 实现，不一定非要用 BFS。 (d) 一个图只要不含三角形，就是二分图。

练习 12.4.4（工程判断） 一个课程表系统要判断"学生选的课有没有时间冲突"：

  • 每门课是一个顶点
  • 如果两门课有学生同时选，就在它们之间连一条边
  • 学生不能同时上两门课，所以要给课"分配时间段"

(a) 这个问题等价于什么图论问题？ (b) 如果图不是二分图，意味着什么？ (c) 如果图不是二分图，实际系统该怎么处理？

练习 12.4.5（挑战·用并查集数连通分量） 本节用 DFS 数连通分量，复杂度 $O(V + E)$。还有一种数据结构叫并查集（Union-Find），它也能做这件事。

(a) 并查集的核心操作是什么？ (b) 对于"边会动态增加"的场景，DFS 和并查集哪个更合适？为什么？ (c) 如果只是"静态地数一次"，两者差别大吗？

八、练习答案

12.4.1

(a) 4 个连通分量。

边：(0,1), (1,2), (3,4), (5,6), (6,7)

  • 分量 1：{0, 1, 2}（0-1-2 是一条链）
  • 分量 2：{3, 4}
  • 分量 3：{5, 6, 7}（5-6-7 是一条链）
  • 分量 4：没有 —— 等等，8 个顶点是 0~7，全部被覆盖了。

所以是 3 个分量：{0,1,2}、{3,4}、{5,6,7}。

(b) 加上 (2,3) 后：2 个分量。

(2,3) 把分量 1 和分量 2 连起来了：

  • 分量 1：{0, 1, 2, 3, 4}
  • 分量 2：{5, 6, 7}

(c) 再加上 (7,0) 后：1 个分量。

(7,0) 把两个分量也连起来了，整个图变成连通的。

所有顶点属于同一个分量：{0,1,2,3,4,5,6,7} ✓

这个练习演示了一个重要性质：加边只会让连通分量"合并"，不会让它们分裂。

达成的条件：一个有 $V$ 个顶点的图，至少需要 $V-1$ 条边才能连通 —— 而且正好 $V-1$ 条时，它必然是一棵树（无环且连通）。

12.4.2

(a) 三色标记推演：

图的结构：0 → 1 → 2 → 3 → 1（3 有一条边回到 1）

步骤 当前 颜色变化 说明
1 0 白色 → 灰色 进入 0
2 1 白色 → 灰色 从 0 进入 1
3 2 白色 → 灰色 从 1 进入 2
4 3 白色 → 灰色 从 2 进入 3
5 — — 3 的邻居是 1，color[1] == 1（灰色）→ 发现环！

所以有环 ✓

环是 1 → 2 → 3 → 1。

注意第 5 步的关键：遇到的是灰色（在当前路径上），所以是环。

如果 1 已经变成黑色了（说明它的所有后代都探索完了），那 3 → 1 就只是一条"交叉边"，不构成环。

(b) 把 3 → 1 改成 3 → 4（4 是新顶点）：没有环。

  0 -> 1 -> 2 -> 3 -> 4

这变成了一条链，无环 ✓

用三色标记推演：0、1、2、3 依次变灰 → 3 走到 4（白色）→ 4 变灰 → 4 没有其他邻居 → 4 变黑 → 回到 3，3 变黑 → 回到 2，2 变黑 → …… → 0 变黑。全程没遇到灰色，所以无环。

12.4.3

  • (a) 错。 两者的判据完全不同： >

    | | 判据 | |---|---| | 无向图 | 遇到"已访问且不是 parent"的邻居 | | 有向图 | 遇到"灰色"的邻居 |

    为什么不能通用？

    无向图里 A—B 意味着 B—A，所以从 B 走到 A 是"原路返回"。

    有向图里 A→B 不意味着 B→A —— 所以"遇到已访问的邻居"可能是正常的交叉（比如两条路径汇聚到同一个顶点），不是环。

    如果把无向图的方法硬套到有向图：会把"菱形"（0→1→3 和 0→2→3）误判成有环 —— 而它显然没有环。

  • (b) 错。 "边数 = 顶点数 - 1"只是树的必要条件，不是充分条件。 >

    反例：4 个顶点、3 条边，但构成一个三角形加一个孤立点：

      0 —— 1        2（孤立）
   \  /
    3

    4 个顶点、3 条边（$V-1 = 3$ ✓），但它有环（三角形）且不连通 —— 不是树。

    树的正确定义：连通 + 无环。

    另一个等价的判据：$V-1$ 条边 且 连通 → 一定是树（这两个条件合起来才充分）。

  • (c) 对。 染色法用 DFS 或 BFS 都可以 —— 因为它的本质是"把相邻顶点的颜色定成相反"，这只需要"从一个点出发扩散到所有可达点"，而 DFS 和 BFS 都能做到。 >

    本节用 BFS 只是因为"按层扩散"的直觉更贴合染色（一层红、一层蓝）。

    用 DFS 的写法：把 queue.Enqueue 换成递归调用即可，逻辑完全一样。

  • (d) 错。 "不含三角形"不等于"不含奇环"。 >

    反例：五边形（5 个顶点围成一圈）—— 它没有三角形（任意三个顶点之间都不构成三角），但有长度为 5 的奇环，所以不是二分图。

    正确的判据：不含任何奇数长度的环。

12.4.4

(a) 等价于"二分图判定"。

两组 = 两个时间段。

  • 如果图是二分图 → 可以用 2 个时间段排完所有课（每组的课放在同一时段，组内没有冲突边）
  • 如果不是二分图 → 2 个时段不够

(b) 不是二分图意味着"至少需要 3 个时间段"。

具体来说：不是二分图 ⟺ 存在奇数长度的环。

最短的奇环是三角形：三门课两两冲突（比如有学生同时选了这三门），必须占用 3 个不同的时段。

(c) 实际系统的处理方式：

先明确一点："最少需要几个时段"这个问题（图着色问题）是 NP 难的 —— 不存在高效的最优算法。

所以实际系统不会去求最优解，而是用启发式算法：

做法 说明
贪心着色 按某种顺序给课分配时段，每门课选"当前不冲突的最小可用时段"——不保证最少，但很快（第 14 章讲贪心）
限定可用时段数 系统固定提供比如 5 个时段，然后检查能不能排下（退化成"判断是否 5-可着色"，仍然 NP 难，但实例小的话可以暴力）
允许冲突 如果实在排不下，提示学生"这两门课冲突了，请改选" —— 把问题交回给用户
迭代改进 先用贪心得到一个解，再用局部搜索（比如模拟退火）优化 —— 工业排课系统的常见做法

这道题的教学意义：

"能把问题建模成图论问题"是一回事，"这个问题好不好解"是另一回事。

二分图判定是 $O(V+E)$（很简单），但"最少几个颜色"（图着色）是 NP 难（很难）。

差的就是"2 种颜色"和"k 种颜色"这一点点 —— 而这正是计算复杂性里最迷人的地方（超出本书范围）。

12.4.5

(a) 并查集的两个核心操作：

操作 作用
Find(x) 找到 $x$ 所在的集合（返回"代表元素"）
Union(x, y) 把 $x$ 和 $y$ 所在的集合合并

用它数连通分量的思路：初始时每个顶点自成一个集合，每遇到一条边就 Union 两端。最后数一下有几个集合，就有几个连通分量。

(b) "边会动态增加"时，并查集更合适。

为什么？

DFS 并查集
静态数一次 $O(V+E)$，一次搞定 $O(E \cdot \alpha(V))$，也很快
加一条边后重新数 要重跑一遍 $O(V+E)$ 只需一次 Union，接近 $O(1)$
加 $m$ 条边 $O(m(V+E))$ $O(m \cdot \alpha(V))$

在"边会不断增加"的场景下，并查集的优势是压倒性的 —— 因为它保留了之前的计算结果，而 DFS 每次都要从头再来。

一个真实的例子：Kruskal 最小生成树算法（超出本书范围）就是靠并查集来判断"加这条边会不会形成环"的 —— 它要不断地加边、不断地判断连通性，正是并查集的主场。

(c) 静态数一次时，两者差别不大。

并查集的 $\alpha(V)$（反阿克曼函数）在实践中几乎是常数（对任何现实规模的输入，$\alpha(V) \le 4$），所以两者都是接近线性的。

选哪个看这些因素：

因素 选择
只需要数一次 都可以，DFS 写起来更直观
边会动态增加 并查集
还需要其他遍历信息（比如路径） DFS（并查集给不了路径）
顶点是字符串等非整数 并查集需要额外做"编号映射"，DFS 用 Dictionary 更直接

并查集的实现极其简洁（十几行代码），但它的优化技巧（路径压缩、按秩合并）很有讲究。这是本书没有覆盖的一块，值得你之后单独学习 —— 它在"连通性"类问题上几乎是标准工具。

九、常见错误

误区 纠正
无向图环检测忘记排除 parent 会把每条边都误判成环（因为无向边是双向的）。
用无向图的方法做有向图环检测 有向图里"已访问的邻居"可能是正常交叉，会被误判成环。要用三色标记。
三色标记里把"黑色"也当成环 灰色才是环。黑色是"探索完毕"，走到那里只是抄近道。
认为"不含三角形就是二分图" 五边形没有三角形，但有 5 环，不是二分图。判据是"不含奇环"。
认为"边数 = V-1 就是树" 还必须连通。反例：三角形 + 孤立点，也是 3 条边。
数连通分量时只从一个起点遍历 只能覆盖一个分量。必须外层遍历所有顶点。

十、本节总结

  1. 连通分量：外层遍历所有顶点，对每个没访问过的启动 DFS。DFS 次数 = 分量个数。实测 4 个分量。
  2. 无向图环检测：DFS 时传 parent，遇到"已访问且不是 parent"的邻居就是环。parent 的作用是排除"来路"。
  3. 有向图环检测：必须用三色标记。遇到灰色（在当前 DFS 路径上）= 有环；遇到黑色（探索完毕）= 交叉边，不是环。
  4. 二分图判定：染色法。二分图 ⟺ 不含奇数长度的环。实测：链 ✅、三角形 ❌、正方形 ✅。
  5. 四个问题都是同一个骨架：DFS/BFS + 一个额外的参数或数组。
  6. 这个视角把"十几个算法"压缩成"两个骨架 + 若干种挂载"。遇到新问题时先问："这是不是某种遍历？我需要额外记录什么？"
  7. "能建模"和"好解"是两回事：二分图判定是 $O(V+E)$，但"最少几种颜色"（图着色）是 NP 难 —— 差的只是颜色数量。

本章小结：第 12 章把图的基础讲完了。

  • 12.1 表示：邻接矩阵 vs 邻接表。稀疏图用邻接表（实测空间差 52.6 倍）。
  • 12.2 DFS：一条路走到底。visited 是灵魂（图有环，没有它会死循环）。
  • 12.3 BFS：一层一层扩散。一定找到最短路径（前提是边权相同）。
  • 12.4 三个应用：连通分量、环检测、二分图 —— 都是骨架上的挂载。

贯穿本章的一条线索："遍历是骨架，问题只是挂载"。

下一章衔接：本章讲的都是"能不能到达"（连通性）。但现实中的图往往带权重 —— 城市之间的距离、任务的耗时、网络的延迟。

"从 A 到 B 的最短路径" 在带权图上就成了一个完全不同的问题。而且还有一个看似简单、实际很深刻的问题："这些任务该按什么顺序做？"（拓扑排序）。下一章讲这两个。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "12.4",
  "title": "连通分量、环检测与二分图",
  "covered": [
    "四个问题的统一视角（骨架 + 挂载）",
    "连通分量的实现与实测（9 顶点 4 分量）",
    "无向图环检测的 parent 参数与实测（三角形 True / 链 False）",
    "「为什么需要 parent」的论证",
    "有向图环检测的三色标记与实测（DAG False / 有环 True）",
    "「无向图方法不能用于有向图」的原因",
    "二分图染色法与实测（链 ✅ / 三角形 ❌ / 正方形 ✅）",
    "「二分图 ⟺ 不含奇环」的规律",
    "图着色是 NP 难的对照（能建模 ≠ 好解）",
    "并查集与 DFS 在动态连通性问题上的对比"
  ],
  "unresolved": [
    "拓扑排序留到 13.1",
    "并查集的完整实现超出本书范围",
    "图着色的 NP 难性超出本书范围",
    "最小生成树超出本书范围"
  ],
  "canonical_terms": {
    "连通分量（Connected Component）": "互相可达的顶点集合",
    "环检测（Cycle Detection）": "判断图中是否存在环",
    "三色标记（Three-Color Marking）": "用白/灰/黑区分未访问、访问中、访问完，用于有向图环检测",
    "二分图（Bipartite Graph）": "顶点能分成两组且每条边都跨组的图，等价于不含奇环"
  },
  "symbols_units": {
    "V": "顶点数",
    "E": "边数"
  },
  "assumptions": [
    "读者已掌握 12.2/12.3 的 DFS 与 BFS",
    "读者理解 12.1 的图表示"
  ],
  "word_count_actual": 3180,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch12/Sec124/",
    "连通分量（4 个）、无向图环检测（True/False）、有向图环检测（False/True）、二分图（True/False/True）均为实测",
    "练习 12.4.1/12.4.2 的推演已手工验算",
    "术语写法与 glossary.md 一致"
  ],
  "next": "13.1 拓扑排序与依赖解析"
}

results matching ""

    No results matching ""