数据结构与算法 / 系统课时
二分图怎样用染色判断
二分图怎样用染色判断
判断一个图是不是二分图,可以转化成一个非常直接的约束:相邻顶点必须使用不同颜色。沿着边不断给顶点交替染成两种颜色,如果某条边最终连接了两个同色顶点,就说明图中存在无法满足二分要求的结构。
学习目标
- 理解二分图、两色染色与奇环之间的等价关系
- 掌握使用 BFS 和 DFS 完成二分图判断的方法
- 正确处理非连通图、自环和染色冲突等边界情况
两色染色为什么能够判断二分图
二分图要求把全部顶点分成两个集合,同一集合内部没有边。因此可以把两个集合分别看成颜色 0 和颜色 1:一条边的两个端点必须颜色不同。
从一个未染色顶点出发,先把它染成 0;访问它的邻居时统一染成 1;再访问下一层时重新染成 0。只要这个过程始终没有冲突,最终所有已访问顶点就形成了一组合法的二分划分。
如果遇到一条边,其两个端点已经被染成相同颜色,就不能通过重新选择起始颜色解决。把整个连通分量的两种颜色整体互换,冲突仍然存在。这种冲突正对应图中出现了奇数长度的环。

BFS 和 DFS 的判断过程
BFS 使用队列按层扩展,非常符合“相邻层颜色交替”的直觉。每取出一个顶点,就检查它的全部邻居:未染色就赋予相反颜色,已经染色则检查是否与当前顶点同色。
DFS 的约束完全相同,只是访问顺序改成沿一条路径深入。无论递归还是显式栈,只要第一次访问顶点时记录颜色,并在遇到已染色邻居时检查冲突,最终判断结果都与 BFS 一致。
对于非连通图,只从一个顶点搜索是不够的。必须遍历所有顶点,每遇到一个尚未染色的顶点,就从它启动一次新的 BFS 或 DFS。只要任意一个连通分量出现冲突,整张图就不是二分图。
用代码实现两种染色方式
下面使用邻接表表示无向图。第一个图由一个四边形和一条独立边组成,可以正常两色染色;第二个图是三角形,其中存在奇环,因此会产生冲突。
from collections import deque
def is_bipartite_bfs(graph):
color = {}
for start in graph:
if start in color:
continue
color[start] = 0
queue = deque([start])
while queue:
u = queue.popleft()
for v in graph[u]:
if v not in color:
color[v] = 1 - color[u]
queue.append(v)
elif color[v] == color[u]:
return False
return True
def is_bipartite_dfs(graph):
color = {}
def dfs(u, current_color):
color[u] = current_color
for v in graph[u]:
if v not in color:
if not dfs(v, 1 - current_color):
return False
elif color[v] == color[u]:
return False
return True
for start in graph:
if start not in color and not dfs(start, 0):
return False
return True
bipartite_graph = {
0: [1, 3],
1: [0, 2],
2: [1, 3],
3: [0, 2],
4: [5],
5: [4],
}
odd_cycle_graph = {
0: [1, 2],
1: [0, 2],
2: [0, 1],
}
print('BFS bipartite:', is_bipartite_bfs(bipartite_graph))
print('DFS bipartite:', is_bipartite_dfs(bipartite_graph))
print('BFS odd cycle:', is_bipartite_bfs(odd_cycle_graph))
print('DFS odd cycle:', is_bipartite_dfs(odd_cycle_graph))预期输出
BFS bipartite: True
DFS bipartite: True
BFS odd cycle: False
DFS odd cycle: FalseBFS 和 DFS 都只会把每个顶点染色一次,并检查每条边有限次。使用邻接表时,时间复杂度都是 ,颜色表以及 BFS 队列或 DFS 调用栈需要 级额外空间。
容易漏掉的边界情况
自环是最直接的冲突。如果顶点存在一条指向自身的边,那么这条边要求同一个顶点同时具有两种不同颜色,因此图一定不是二分图。上面的实现会在检查该邻居时发现颜色相同并返回 False。
输入邻接表还应与问题的图模型一致。对于无向图,一条边通常应在两个端点的邻接表中都出现;如果只记录单向关系,搜索可能遗漏本应检查的约束。若原问题是有向图,则应先明确所谓“二分”是按方向定义,还是忽略方向后判断其底层无向图。
实际选择 BFS 还是 DFS 通常不会改变复杂度。需要按层观察染色过程、避免深递归时更适合 BFS;已有 DFS 框架或还要同时完成连通分量遍历时,DFS 往往更顺手。真正决定正确性的不是搜索顺序,而是每条边都必须满足两端颜色相反这一约束。