专题进阶 · 图算法推荐总顺序 · 第 60 / 148 课

用两色约束检测二分图,理解奇环为何是不可二分的障碍。

先学会这些,再进入本课 广度优先搜索 连通分量
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 图算法

二分图Bipartite Graph

节点能分成两组且组内无边;用两色染色检查,奇环会造成冲突。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

用两色约束检测二分图,理解奇环为何是不可二分的障碍。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

把一张无向关系图中的节点分成两组,要求每条边两端属于不同组。怎样判断是否可能?

02一步步得到方法

分组不是按编号或度数猜测

先任取未染色节点设为 0,对其邻居要求颜色为 1,对邻居的邻居要求 0,以 BFS 传播。发现一条边两端已同色,就出现矛盾。不同连通分量可独立选择起始颜色。

二分图不要求两组数量相同,也不要求每组内部节点相互连通。孤立点可放任何一侧;自环要求一个节点与自己异色,立即不可能。

奇环为何导致冲突

沿环每走一条边颜色翻转一次。偶数条边后能回到原色,奇数条边后却要求原节点变成另一色,所以奇环不可能两染色。反过来,BFS 染色冲突可追溯两条树路径和冲突边,构造奇环。

边约束比层号更根本

二分图要求每条边两端颜色不同。BFS 从一个点染色后,给未染色邻居相反颜色;若发现同色相连,就无法满足这条边约束。每个未访问分量都需要重新选起点。

沿环交替染色,偶数步可回到原色,奇数步则要求起点同时拥有两种颜色,所以奇环是冲突来源。自环本身就是长度1的奇环,应直接判失败。

03把一个小例子完全算清楚

环 0–1–2–3–0,再考虑三角形 0–1–2–0。

步骤计算与状态为什么这样做
四环起点 0颜色 0邻居 1、3 染 1
节点 2经 1 染 0与 3 的颜色不同,合法
三角形1、2 都被 0 染为 1边 1–2 冲突

窄屏可左右滑动表格,阅读完整计算与理由。

偶环可二分,奇环不可;是否有环本身不是判断标准。

04为什么这个方法成立

  1. 传播时每条新树边均连接异色节点。
  2. 若扫描所有边均无冲突,最终颜色直接给出合法二分。
  3. 若冲突,则该约束无法同时满足,图含奇环,不能二分。

05把推导翻译成代码

Python · 可独立运行的教学实现

from collections import deque
def bipartite(n, edges):
    adj = [[] for _ in range(n)]
    for u,v in edges:
        adj[u].append(v); adj[v].append(u)
    color = [-1]*n
    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = 1-color[u]; q.append(v)
                elif color[v] == color[u]:
                    return None
    return color

逐个理解关键决定

1-color[u]
在 0、1 两色之间翻转。
for start in range(n)
检查所有分量,不能让另一个分量中的奇环漏检。

06时间、空间与实现范围

时间 O(V+E),颜色与队列 O(V),邻接表 O(V+E)。

颜色分组只是可行划分,不是最大匹配,后者还要选择不共享端点的边。

07改变条件,检查哪里会出错

有环就不是二分图

偶环可以,两色失败的关键是奇环。

仅检查起点所在分量

其他分量也可能有奇环,外层必须遍历所有未染色节点。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

一棵树一定二分吗?

需要一点提示

按深度奇偶染色。

查看解析与答案

是,树无环,父子深度差 1,始终异色。

练习 2 · 边界与辨析

单个自环如何判断?

需要一点提示

边两端其实同一节点。

查看解析与答案

返回 None。

练习 3 · 变式与迁移

二分组是否唯一?

需要一点提示

连通分量可整体换色。

查看解析与答案

每个非平凡连通分量可整体交换两色;不连通图有独立选择。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 图算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。