染色法判定二分图：原理与实现详解
染色法判定二分图：原理与实现详解
二分图判定是图论中的一个重要问题，广泛应用于网络流、匹配算法等领域。本文将详细介绍如何使用染色法判断一个图是否是二分图，包括算法原理、实现细节，并配有图示和完整代码，帮助读者深入理解这一算法。
前言
本篇博客讲解二分图判定之染色法，它的时间复杂度是O ( n + m ) O(n + m)O(n+m)，n表示点的数量，m表示边的数量。
题目
题目链接：860. 染色法判定二分图
给定一个n nn个点m mm条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数n nn和m mm。
接下来m mm行，每行包含两个整数u uu和v vv，表示点u uu和点v vv之间存在一条边。
输出格式
如果给定图是二分图，则输出
Yes
，否则输出
No
数据范围
1 ≤ n , m ≤ 1 0 5 1≤n,m≤10^51≤n,m≤105
输入样例：
4 4
1 3
1 4
2 3
2 4
输出样例：
Yes
什么是二分图？
做本题之前首要要清楚二分图的概念。
有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中，每个顶点集中没有边直接相连接！
说人话的定义：图中点通过移动能分成左右两部分，左侧的点只和右侧的点相连，右侧的点只和左侧的点相连。
下图就是个二分图：
- 下图不是个二分图（集合内的点有连通）：
如何判断一个图是不是二分图？
当且仅当图中不含奇数环（如下图所示，数字1代表一个集合，数字2代表另一个集合，如果该环是奇数环的话，也就是该环的点的个数是奇数个，那么必然会发生冲突即某一点即被标记为1又被标记为2）
开始对任意一未染色的顶点染色。
判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色。
若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。
bfs和dfs可以搞定！（注意，Python中dfs会发生爆栈，所以本题用bfs来求解）
详细代码
# 导入双端队列deque，用于广度优先搜索（BFS）
from collections import deque
# 读取图的顶点数n和边数m
n, m = map(int, input().split())
# 初始化一个列表num，用于存储图的邻接表表示
# num[i]存储与顶点i直接相连的所有顶点
num = [[] for i in range(n + 1)] # 列表大小为n+1，因为顶点编号从1开始
# 读取m条边，构建图的邻接表
for i in range(m):
a, b = map(int, input().split())
num[a].append(b) # 边a-b
num[b].append(a) # 边b-a，因为是无向图
# 初始化一个列表color，用于存储每个顶点的颜色
# 0表示未着色，1和2表示两种不同的颜色
color = [0] * (n + 1)
# 定义广度优先搜索函数bfs，用于检查从顶点x开始的着色是否满足二分图条件
def bfs(x):
q = deque() # 创建一个双端队列
q.append((x, 1)) # 将顶点x加入队列，并着色为1
while q: # 当队列不为空时循环
i, c = q.popleft() # 从队列左侧取出一个元素（顶点及其颜色）
for j in num[i]: # 遍历与顶点i相连的所有顶点
if color[j] == 0: # 如果顶点j未着色
# （3 - 1 = 2， 如果 i 的颜色是2，则和 i 相邻的染成 1）
# （3 - 2 = 1， 如果 i 的颜色是1，则和 i 相邻的染成 2）
color[j] = 3 - c # 着色为与顶点i不同的颜色
q.append((j, 3 - c)) # 将顶点j及其颜色加入队列
if color[j] == c: # 如果顶点j与顶点i颜色相同
return False # 发现冲突，不是二分图
return True # 所有顶点着色完成且未发现冲突，是二分图
# 标记是否所有顶点都满足二分图条件
flag = 1
# 遍历每个顶点，如果顶点未着色，则进行bfs着色检查
for i in range(1, n + 1):
if color[i] == 0:
if not bfs(i): # 如果从顶点i开始的bfs检查失败
flag = 0
break # 提前结束循环
# 根据检查结果输出
if flag:
print("Yes") # 所有顶点都满足二分图条件
else:
print("No") # 存在不满足二分图条件的顶点