判断二分图——染色法

77 阅读 0 评论 51 点赞

我是靠谱客的博主粗暴钢笔，这篇文章主要介绍判断二分图——染色法，现在分享给大家，希望可以做个参考。

怎么判定一个图是否为二分图
从其中一个定点开始，将跟它邻接的点染成与其不同的颜色，最后如果邻接的点有相同颜色，则说明不是二分图，每次用bfs遍历即可。
代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <queue>

#include <cstring>

#include <iostream>

using namespace std;
const int N = 999;
int col[N], Map[N][N];
//0为白色，1为黑色

bool BFS(int s, int n)
{
queue<int> p;
p.push(s);
col[s] = 1;
//将搜索起始点涂成黑色
while(!p.empty())
{
int from = p.front();
p.pop();
for(int i = 1; i <= n; i++)
{
if(Map[from][i] && col[i] == -1) //如果从from到i的边存在（为邻接点） && i点未着色
{
p.push(i);
//将i点加入队列
col[i] = !col[from];//将i点染成不同的颜色

}
if(Map[from][i] && col[from] == col[i])//如果从from到i的边存在（为邻接点） && i点和from点这一对邻接点颜色相同，则不是二分图

return false;
}
}
return true;
//搜索完s点和所有点的关系，并将邻接点着色，且邻接点未发现相同色则返回true

}
int main()
{
int n, m, a, b;
memset(col, -1, sizeof(col));
cin >> n >> m;
//n 为有多少点，m为有多少边

for(int i = 0; i < m; i++)
{
cin >> a >> b;
Map[a][b] = Map[b][a] = 1;
}
bool flag = false;
for(i = 1; i <= n; i++)
//遍历并搜索各个连通分支
{
if(col[i] == -1 && !BFS(i, n)) //每次找没有着色的点进行判断，如果从它开始BFS发现相同色邻接点则不是二分图
{
flag = true;
break;
}
}
if(flag)
cout << "NO" <<endl;
else
cout << "YES" <<endl;
return 0;
}