导读:什么是二分图?
二分图的顶点集V可分割为两个互不相交的子集A和B,而且图中的任意一条边的两个端点,都是一个端点属于集合A,另一个端点属于集合B。如下图:
二分图的特点/判断
一个图是二分图的充分必要条件是
至少有两个顶点,而且要么没有回路,要么只有边数为偶数的回路。
为了对这个结论有更具体的认识,我们举个例子看一下,下面先展示一个有环二分图。
[HTML_REMOVED]
红色的就是环,大家可以尝试一下画环,你们会发现,只要是二分图,无论怎么造环,这些环的边一定是偶数的,如果你造出了奇数边的环,就说明你破坏了二分结构。你们想想,环肯定是连通两个集合的,集合A伸出一条边伸进集合B,集合B就一定要还一条边回来,一来一回必是偶数,如果出现了奇数那肯定是某集合内部联通了。
有人会有疑问,但如果两个集合内部都联通了,那不也是偶数环吗?那还是二分图吗?
看下图:
不难发现,这样的图形其实也是二分图,只不过是点的位置误导了我们而已。
判断二分图的算法
染色法是用于判断二分图的算法,算法流程如下:
- 步骤一:随便找一个连通块,随便找一个起点,将其染色。
- 步骤二:接着遍历这个连通块中的点,将这些点染成与相连点相反的颜色。
- 如果出现矛盾,说明不是二分图。
- 如果无矛盾:
- 图中所有的连通块都染好色了,说明这个图是二分图。
- 还有未染色的连通块,执行步骤一。
接下来看代码实现模板(c++)
#include<iostream>
const int N = xxxxxx, M = xxxxxxx
//用邻接表存图模板,
//一般二分图都是无向图,所以存边要记得正反各存一次
int h[N],e[M],ne[M],idx;
void add(int a,int c)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void init()
{
memset(h,-1,sizeof h);
}
//染色法模板
//color[k]=a,表示点k的颜色是a
int color[N];
//这个dfs的作用是,判断这样染色会不会出现矛盾
bool dfs(int u ,int c)
{
color[u]=c;//先给自己染色再深搜
//遍历与自己相连的点
for(int i = h[u];i!=-1;i=ne[i])
{
int j = e[i];
if(!color[j])//如果这个点还未被染过色
if(!dfs(j,3-c))//就染成相反色,调用dfs看看会不会矛盾(这里把1,2作为相反色)
return false;
else if(color[j]==c)
return false;
}
return true;
}
为了更好记忆这个代码的步骤,下面简单模拟一下:
练习例题:染色法判断二分图
AC代码
#include<iostream>
#include<cstring>
using namespace std;
//无向图,存两条边,N*2
const int N = 2*100010;
int h[N],ne[N],e[N],w[N],idx;
//记录点的颜色 , 1 是黑色 ,2是白色
int color[N];
int n,m;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool dfs(int u,int c)
{
color[u]=c;//先染色!!!
for(int i=h[u];i!=-1;i=ne[i])
{
int j = e[i];
if(!color[j])//如果未染色
{
if(!dfs(j,3-c))
return false;
}
else if(color[j]==c)
return false;
}
return true;
}
int main()
{
memset(h,-1,sizeof h);
cin>>n>>m;
for(int i = 0 ; i < m ;i ++)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
bool flag = true;
for(int i = 1 ; i<=n ;i ++)
{
if(!color[i])//no clor
if(!dfs(i,1))//what ever color
{
flag = false;
break;
}
}
if(flag)
puts("Yes");
else
puts("No");
return 0;
}