二分图判定
📌 定义
**二分图（Bipartite Graph）**是指可以将顶点分成两个不相交的集合，使得每条边的两个端点分别属于不同的集合。
二分图示例:
A组: 0, 2, 4
B组: 1, 3, 5
0---1
| |
2---3
|
4---5
非二分图（含奇数环）:
0---1
|\ /|
| X |
|/ \|
2---3
核心思路
- 染色法：用两种颜色给节点染色
- 相邻异色：相邻节点必须是不同颜色
- 奇数环：存在奇数环则不是二分图
- BFS/DFS：使用BFS或DFS进行染色
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(V+E) | 遍历所有节点和边 |
| 空间复杂度 | O(V) | 颜色数组 |
Go 代码
Go 实现
package main
func IsBipartiteBFS(graph [][]int, n int) bool {
color := make([]int, n)
for i := range color {
color[i] = -1
}
for start := 0; start < n; start++ {
if color[start] != -1 {
continue
}
queue := []int{start}
color[start] = 0
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for _, neighbor := range graph[node] {
if color[neighbor] == -1 {
color[neighbor] = 1 - color[node]
queue = append(queue, neighbor)
} else if color[neighbor] == color[node] {
return false
}
}
}
}
return true
}
func IsBipartiteDFS(graph [][]int, n int) bool {
color := make([]int, n)
for i := range color {
color[i] = -1
}
var dfs func(int, int) bool
dfs = func(node, c int) bool {
color[node] = c
for _, neighbor := range graph[node] {
if color[neighbor] == -1 {
if !dfs(neighbor, 1-c) {
return false
}
} else if color[neighbor] == c {
return false
}
}
return true
}
for i := 0; i < n; i++ {
if color[i] == -1 {
if !dfs(i, 0) {
return false
}
}
}
return true
}思路展开
染色法原理
- 初始化：所有节点未染色
- 选择起点：选择未染色节点，染成颜色0
- BFS/DFS：
- 访问邻接节点
- 如果未染色，染成相反颜色
- 如果已染色且颜色相同，返回false
- 重复：处理所有连通分量
执行示例
图:
0---1
| |
2---3
BFS染色过程:
初始: color=[-1,-1,-1,-1]
从节点0开始:
color[0]=0, queue=[0]
处理节点0:
邻接节点1: color[1]=1, queue=[1]
邻接节点2: color[2]=1, queue=[1,2]
处理节点1:
邻接节点0: 已染色，颜色不同 ✓
邻接节点3: color[3]=0, queue=[2,3]
处理节点2:
邻接节点0: 已染色，颜色不同 ✓
邻接节点3: 已染色，颜色不同 ✓
处理节点3:
邻接节点1: 已染色，颜色不同 ✓
邻接节点2: 已染色，颜色不同 ✓
结果: 是二分图
分组: A={0,3}, B={1,2}
经典题目
💡 优缺点
优点
- ✅ 算法简单直观
- ✅ 时间复杂度O(V+E)
- ✅ 可以同时得到分组
缺点
- ❌ 只能判断是否为二分图
- ❌ 不能处理加权图