1. 概述
在图论中，二分图（Bipartite Graph）是一种特殊的图结构，由两个顶点集合构成。本文将介绍二分图的定义、性质，并提供一个判断给定图是否为二分图的算法。
2. 二分图定义
设图 G(V, E)，它是一个二分图当且仅当：
- 顶点集合 V 可以划分为两个互不相交且独立的子集 V₁ 和 V₂
- 所有边 E 的两个端点分别属于 V₁ 和 V₂
换句话说，图中每条边都连接两个不同集合中的顶点。
3. 示例
来看一个二分图的例子：
上图 G₁(V, E) 中的顶点集为 V = {A, B, C, D, E}，我们可以将其划分为两个子集：
- V₁ = {A, D}
- V₂ = {B, C, E}
观察边集合 E = {E₁, E₂, E₃, E₄, E₅, E₆}，每条边的一个端点在 V₁，另一个在 V₂。没有边连接两个同属 V₁ 或 V₂ 的顶点。
因此，该图满足二分图的定义。
4. 二分图性质
二分图具有以下重要特性：
✅ 不含奇数长度的环
二分图中不可能存在长度为奇数的环。
✅ 所有子图也是二分图
原图是二分图，则其任意子图也一定是二分图。
✅ 2-可染色性
可以用两种颜色对图中所有顶点进行染色，使得任意相邻顶点颜色不同。
✅ 无向图中两个划分集合的度数和相等
在无向二分图中，两个划分集合中所有顶点的度数之和相等。
5. 判断算法
我们可以使用广度优先搜索（BFS）结合图染色法来判断一个图是否为二分图。
✅ 算法步骤
algorithm IsBipartite(G(V, E), S):
// INPUT
// G(V, E) = a graph with vertices V and edges E
// S = starting vertex
// OUTPUT
// Flag indicating if the graph is bipartite
r <- create an empty queue
color[S] <- RED
r.enqueue(S)
while r is not empty:
n1 <- r.dequeue()
for each n2 in n1.Adj():
if color[n2] = null:
if color[n1] = RED:
color[n2] = BLUE
else:
color[n2] = RED
r.enqueue(n2)
else:
if color[n2] = color[n1]:
return 'Graph is not Bipartite'
return 'Graph is Bipartite'
✅ 算法说明
- 初始化：将起始顶点染为红色
- BFS 遍历过程中，对当前顶点的所有邻接顶点进行染色（与当前顶点颜色不同）
- 如果某个邻接顶点已被染色且颜色与当前顶点相同，则说明图不是二分图
- 否则继续 BFS，直到所有顶点都被处理
✅ 实现要点
- 使用队列进行 BFS
- 使用颜色数组记录每个顶点的颜色（RED / BLUE）
- 如果图是连通的，从任意一个顶点开始即可；如果是非连通图，需要对每个未访问顶点重复该过程
6. 算法执行示例
我们以一个图 G₂(V, E) 为例，顶点集合为 {A, B, C, D, E, F}，选择 A 作为起始顶点：
- 染色 A 为红色
- A 的邻接顶点 B 和 D 染为蓝色
- B 的邻接顶点 C 和 E 染为红色
- D 的邻接顶点 C（已染色）和 F 染为红色
- 继续检查所有邻接顶点颜色是否冲突
最终结果：
所有相邻顶点颜色不同，说明该图是二分图。
7. 时间复杂度分析
- 整个算法基于 BFS，每个顶点和边最多被访问一次
- 若使用邻接表存储图结构，时间复杂度为 O(V + E)
- 若使用邻接矩阵存储，则时间复杂度为 O(V²)
8. 小结
本文介绍了二分图的定义、性质，并提供了一个基于 BFS 和图染色的判断算法。该算法具有较高的效率和实用性，适用于大多数图结构判定场景。
- ✅ 二分图是图论中一种重要结构
- ✅ 判断算法基于 BFS + 图染色法
- ✅ 时间复杂度取决于图的存储方式（邻接表 O(V + E)，邻接矩阵 O(V²)）
- ❗ 注意：如果图是非连通的，需要对每个连通分量分别执行判断逻辑
掌握该算法对解决图着色、匹配等问题有重要意义，是图算法中的基础之一。