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为什么这个方法成立
- 传播时每条新树边均连接异色节点。
- 若扫描所有边均无冲突,最终颜色直接给出合法二分。
- 若冲突,则该约束无法同时满足,图含奇环,不能二分。
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,始终异色。
单个自环如何判断?
需要一点提示
边两端其实同一节点。
查看解析与答案
返回 None。
二分组是否唯一?
需要一点提示
连通分量可整体换色。
查看解析与答案
每个非平凡连通分量可整体交换两色;不连通图有独立选择。