aaa
2026-04-23 18:47:07
发布于：北京
28阅读
0回复
0点赞
fjsdjflkdsflsdjflkdsjfklsjflksjfkljlksjflkdjkflsdjfklsdjlkgfjslkjdf
二分图染色讲解
一、核心基础概念
1. 二分图定义
二分图，又称作二部图，是一种特殊的无向图。
它的所有顶点可以被划分成两个互不相交的独立集合，满足：
- 图中任意一条边的两个端点，一定分属两个不同的集合
- 同一个集合内部的任意两个顶点，没有直接相连的边
简单理解：把整张图的点分成黑白两组，所有连线都只能是「黑→白」，绝对不能出现「黑→黑」的连线或者「白→白」的连线。
2. 二分图染色的本质
二分图染色就是二分图判定的标准算法，核心逻辑：
用两种颜色对图中所有节点进行标记，相邻节点必须染成不同颜色；如果染色过程中出现冲突（相邻节点颜色相同），则这张图不是二分图。
3. 二分图的核心判定定理
一张无向图是二分图，当且仅当图中不存在奇数长度的环（奇环）。
- 有偶环（4、6、8个节点的环）：可以正常二分染色，是二分图
- 有奇环（3、5、7个节点的环）：染色必然冲突，不是二分图
二、二分图染色算法规则
基础约定
- 用数组
color[]记录每个节点的颜色 color[u] = 0：表示节点u未被染色、未被访问color[u] = 1 / 2：两种区分颜色，代表两个不同集合
染色核心规则
- 从一个未染色的起点出发，先给起点染成颜色1
- 遍历当前节点的所有相邻节点：
- 相邻节点未染色：染成和当前节点相反的颜色（1与2互换），继续递归/遍历
- 相邻节点已染色：判断颜色是否和当前节点冲突
- 颜色相同：直接判定不是二分图，染色失败
- 颜色不同：合法，跳过该节点
- 图可能不连通，必须遍历所有未染色的节点，分别执行染色
三、两种标准实现模板
通用说明
- 基于DFS/BFS基础扩展
- 采用邻接表存储，适配考级大数据范围
※ 模板1：DFS深度优先染色 ※
#include <bits/stdc++.h>
using namespace std;
const int N = 1111;
vector<int> g[N];
int color[N];
bool is_eft = true;
// u:当前节点 c:当前节点要染的颜色
void dfs(int u, int c) {
if (!is_eft) return;
color[u] = c;
for (int v : g[u]) {
if (color[v] == 0) {
dfs(v, 3 - c);
} else if (color[v] == c) {
is_eft = false;
return;
}
}
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1;i <= m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1;i <= n; i++) {
if (color[i] == 0) {
dfs(i, 1);
}
}
cout << (is_eft ? "Yes" : "No");
return 0;
}
※ 模板2：BFS广度优先染色 ※
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1111;
vector<int> g[N];
int color[N];
bool is_eft = true;
void bfs(int now){
if (is_eft == false){
return ;
}
color[now] = 1;
queue<int> q;
q.push(now);
while(!q.empty() && is_eft){
int f = q.front();
q.pop();
for (int now : g[f]){
if (color[now] == 0){
color[now] = 3 - color[f];
q.push(now);
} else if (color[now] == color[f]){
is_eft = false;
return ;
}
}
}
}
int main(){
cin >> n >> m;
for (int i = 1;i <= m;i++){
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1;i <= n;i++){
if (color[i] == 0){
bfs(i);
}
}
cout << (is_eft ? "Yes" : "No");
return 0;
}
四、考场高频易错点
-
必须处理非连通图
绝大多数考生丢分点：只遍历起点，忽略了图中不连通的独立子图，只要有一个子图不是二分图，整张图就不是二分图。 -
无向图要双向存边
读入边u->v时，必须同时把v加入u的邻接表、u加入v的邻接表，少写一句直接染色错误。 -
冲突后必须提前剪枝
发现冲突后不要继续遍历，直接终止算法，避免无效运行、逻辑混乱。 -
颜色初始值必须为0
不能用1、2作为未标记状态，0是固定约定，避免和染色值冲突。 -
二分图染色只适用于无向图
有向图不能直接用这套染色逻辑 -
如果有任意一个节点未被染色，都要从当前节点开始bfs/dfs
五、核心内容速记总结
- 二分图：点分两组，边只跨组，无同组边，无奇环。
- 染色规则：相邻异色，冲突则非二分图。
- 反色公式：，1和2快速互换。
- 关键操作：遍历所有未染色节点，处理非连通图。
有帮助，赞一个