二分图检查器

伪代码

一个图是二分图，当且仅当它可以用两种颜色着色。因此这项检测就是一次遍历：把每个结点染成与其父结点相反的颜色，并留意是否出现冲突。

是否二分图(图):
    颜色 = {} // 所有结点均未着色

    对每个尚未着色的结点 s:      // 覆盖每个分量
        颜色[s] = 0
        队列 = [s]
        当队列非空时:
            u = 队列.取出()
            对 u 的每个邻居 v:
                若 v 尚未着色:
                    颜色[v] = 1 - 颜色[u]
                    队列.放入(v)
                否则若 颜色[v] == 颜色[u]:
                    返回 假        // 发现奇环

    返回 真

这个冲突并不是一个随意的失败信号，而是一份证明。若两个相邻结点被染上同一种颜色，那么从它们各自沿树边回到最近公共祖先的两条路径，再加上这条连接边，就构成了一个奇数长度的环。二分图恰恰就是不含奇环的图，因此这条冲突边是一份可以交还给调用方的凭证。

分步示例演算

先给一个四元环做二着色，再加入一条弦，看同一次遍历如何把它判否。

示例图: 先是四元环 A-B、B-C、C-D、D-A。随后是同一个图再加上弦 A-C。

1. 从 A 开始给四元环着色. A 染成颜色 0。它的邻居 B 与 D 染成颜色 1。从 B 出发，邻居 C 尚未着色，染成 0。从 D 出发，邻居 C 已染为 0，而 D 是 1，这是合法的差异，因此没有冲突。
2. 四元环的结果. 颜色为 A 0、B 1、C 0、D 1。该图是二分图，两部分为 {A, C} 与 {B, D}。每条边都跨接两部分，没有任何一条落在某一部分内部。
3. 加入弦 A-C. A 与 C 的颜色都是 0，因此这条弦现在连接了同一部分中的两个结点。从 A 重新遍历：A 染 0，而它的邻居 B、D 以及此时的 C 都染成 1。
4. 冲突浮现. 在处理颜色为 1 的 B 时，它的邻居 C 的颜色同样是 1。这是一条落在同一部分内部的边，因此算法在边 B-C 处返回假。
5. 为什么这条弦会破坏二分性. 这条弦造出了三角形 A-B-C，即一个长度为 3 的环。奇环无法用两种颜色着色：沿奇环交替着色走一圈后回到起点，会要求它取与已有颜色相反的那一种。

四元环是二分图，两部分为 {A, C} 与 {B, D}；加入弦 A-C 后它不再是二分图，冲突在边 B-C 处被检出。请注意它所展示的一般规律：所有偶环都是二分的，所有奇环都不是，因此单凭环的长度就能决定结果。另外也请注意，冲突是在边 B-C 上报告的，而不是在那条弦本身上，这是正常的，因为算法报告的是矛盾最先暴露的位置，而不是你会归咎的那条边。

复杂度及其来源

时间: O(V + E) · 空间: O(V)

这是一次 BFS 或 DFS，每条边只做一次比较，因此代价恰好等于一次遍历。每个结点着色一次，每条边从两个端点各检查一次。空间是每个结点一个颜色，再加上队列或递归栈，都是 O(V)。对所有结点的外层循环在渐进意义上不增加任何代价，而它正是让非连通图也能正确工作的关键。不存在更快的方法，因为判定二分性必须查看每一条边：任何一条未被检查的边都可能正是造出奇环的那一条。

何时使用二分图检查，何时不宜

二分性通常是一个前置条件而非目标。之后要做什么，取决于你当初为何要问这个问题。

常见陷阱

• 只从一个结点出发遍历. 非连通图只有在每个分量都是二分图时才是二分图。只从单一源点出发只检查了一个分量，会让一个在别处含有奇环的图悄悄通过。请遍历所有结点，并从每个尚未着色的结点重新发起遍历。
• 把「未着色」当成一种颜色. 用 0 同时表示「未访问」和「第 0 部分」，会让冲突判断失灵。请使用单独的哨兵值，例如 -1，或者用「不在映射中」来表示，以便区分「尚无颜色」与「颜色为 0」。
• 忘记自环是致命的. 自环是一个长度为 1 的奇环，它会立刻让图不再是二分图。而跳过父结点的遍历可能完全察觉不到它，因此请显式检查自环。
• 误以为无环才是值得关注的情形. 任何树和森林都平凡地是二分图，因为它们根本没有环。只有当环出现时这项检测才有意义，因此在树形输入上顺利通过并说明不了什么。
• 不做对称化就用在有向图上. 二分性是无向图的性质。在有向图上你必须先决定单向边是否算作相邻，并对边做对称处理，否则这个问题根本没有良定义的答案。

常见问题

什么是二分图？

二分图是指其结点可以划分为两个集合，使得每条边都连接一个集合中的结点与另一个集合中的结点，而任一集合内部都没有边。等价地说，它是可以用两种颜色正确着色的图；再等价地说，它是不含奇数长度环的图。

如何检查一个图是否是二分图？

执行一次 BFS 或 DFS，把每个新到达的结点染成与来源结点相反的颜色。若发现某条边的两个端点已经同色，该图就不是二分图。请从每个尚未着色的结点重复这一过程，以覆盖所有分量。整项检测为 O(V + E)。

为什么奇环是决定性因素？

因为沿任意一条路径颜色都必须交替。绕偶数长度的环走一圈，会以出发时的颜色回到起点，这是自洽的。绕奇数长度的环走一圈，回到起点时却需要与已分配颜色相反的那一种，这就是矛盾。因此一个图是二分图，当且仅当它不含奇环。

检查二分性的时间复杂度是多少？

O(V + E) 时间和 O(V) 空间。它是一次遍历，每条边做一次颜色比较。这是最优的，因为任何一条未被检查的边都可能正是造出奇环的那一条，所以每条边都必须看过。

二分图有什么用途？

用于刻画任何两侧之间的关系：求职者与岗位、学生与课程、买方与卖方、文档与词项。一旦确定某个图是二分图，最大匹配就可以用 Hopcroft-Karp 高效求解，而这正支撑着指派问题、排程与推荐系统。