Computing · Algorithms
Bipartite Graph (2-Coloring Test)
二分图判定
~ 9 min · v1
二分图判定
cs-algo/bipartite-graph · COMP2521
0 / 3
1 先看：能用两种颜色染点、让每条边两端都不同色吗？
给你一张图，问：能不能把所有点只用两种颜色染色，使得每条边的两个端点颜色都不一样？能做到，它就是二分图。点「下一步」用 BFS 试着染：起点先红，它的邻居必须蓝，邻居的邻居又必须红……一层层交替。再点「换成有奇环的图」看会发生什么。
BFS 二染色判定
BFS 队列（还没开始）
颜色 0（红）颜色 1（蓝）橙圈 = 当前处理的点
点「下一步」：从 A 开始，给它染颜色 0。
二分图（Bipartite Graph）：顶点能分成两个互不相交的组，使得每条边都横跨两组（组内没有边）。等价说法：能用两种颜色给点染色，让每条边两端异色。
判定方法：BFS / DFS 染色——起点任选一色，每访问一条边就把对面染成相反色；若发现某条边两端已是同色，则不是二分图。复杂度 O(V+E)。
2 凭什么对：同色冲突 ⟺ 存在奇环
BFS 染色看着只是"交替涂色"，但它恰好抓住了二分图的本质。
交替染色 = 强制约束
沿着边走，颜色必须 0、1、0、1…… 交替。每条树边自动满足"两端异色"，无需检查。
冲突只可能在"非树边"
当遇到一条连向已染色点的边、且两端同色，说明从该点出发绕回来用了偶数步，加上这条边构成一个奇数长度的环。
奇环 ⟺ 非二分图
定理：图是二分图 当且仅当 它不含奇环。所以"染色出现同色边"正是"存在奇环"的信号。
别忘了：图可能不连通。要对每个还没染色的点各起一次 BFS/DFS，否则会漏掉某些连通块。只要任意一块出现同色冲突，整张图就不是二分图。
3 二分图有什么用
"两组、边只跨组"的结构在现实里非常常见。
匹配问题
求职者↔岗位、学生↔课程、任务↔机器：把两类东西配对，正是二分图匹配（如匈牙利算法、最大匹配）。
冲突 / 分组
把对象分成两派使"有矛盾的不在同一派"——本质就是二染色，可染则可分。
建模检验
很多算法假设输入是二分图。先用 O(V+E) 染色判定，是上层算法的前置检查。
常见误区："边很多"或"是完全图"并不代表不是二分图；"无环"也不是二分图的条件——二分图可以有环，只要环都是偶数长度。判据只有一个：没有奇环（等价于能二染色）。
4 自测
三道题，点选项即时判对错。
去做例题：用 BFS 判断一张图是否为二分图
去做例题
一句话带走：
二分图 = 顶点能分两组、边只跨组 = 能用两种颜色染点使每条边两端异色。判定用 BFS/DFS 染色：起点一色、沿边交替染对面，发现同色边就说明有奇环、不是二分图，复杂度 O(V+E)。核心定理：二分图 ⟺ 不含奇环。图不连通时记得对每个未染色点都起一次。常用于匹配、分组等问题。