染色法判断是否是二分图

二分图：把无向图G= (V,E)分为两个集合V1,V2，所有的边都在V1和V2之间，集合内部是没有边的。V1的一个点和V2的一个点关联，称为一个匹配

一个图是否为二分图，一般用染色法来进行判断，一条边连接的两个顶点颜色不相同，用两种颜色对所有边进行染色。染色结束后，若所有相邻顶点的颜色不同，那么就是二分图，
一个图是二分图，当且仅当他不含奇数边数的圈

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
const int M = 2 * N;
int Head[N],Value[M],Next[M],Index;//邻接表 
int n,m;//n节点个数 m边个数 
int Color[N];//0代表未被染色,1,2代表两种不同颜色 
//加边 
void AddEdge(int Start, int End)
{
Value[Index] = End;
Next[Index] = Head[Start];
Head[Start] = Index;
Index++;
}
//对第i个节点 染col色 
bool DFS(int i, int col)
{
//将节点i染上色 
Color[i] = col;
//遍历i的邻居 
for(int j = Head[i]; j != -1; j = Next[j])
{
//与i相连的节点 
int k = Value[j];
//如果这个节点没有被染过色 
if(!Color[k])
{
if(!DFS(k,3-col))
{
return false;
}
}
//如果当前节点和他的邻居染相同的颜色 则不是二分图 
else if(col == Color[k])
{
return false;
}
}
return true;
}
int main(int argc, char** argv)
{
scanf("%d%d", &n, &m);
memset(Head, -1, sizeof(Head));
for(int i = 0; i < m; i++)
{
int Start,End;
scanf("%d%d", &Start, &End);
//无向图 
AddEdge(Start,End);
AddEdge(End,Start);
}
bool flag = true;
for(int i = 1; i <= n; i++)
{
//如果没有进行染色 
if(!Color[i])
{
//如果染色失败 发生矛盾 
if(!DFS(i,1))
{
flag = false;
break;
}
}
}
if(flag)
{
printf("Yesn");
}
else
{
printf("Non");
}
return 0;
}```

最后

以上就是平常咖啡为你收集整理的染色法判断是否是二分图的全部内容，希望文章能够帮你解决染色法判断是否是二分图所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。