图论——二分图1:二分图以及判定

 

图,有有向图,无向图,稠密图,简单图······

算法,有贪心法,二分法,模拟法,倍增法······

 

那,二分图是啥?

二分法+有向图?

 

图论——二分图1:二分图以及判定

 

于是,我查了许多资料,才对它有一定了解。

 

二分图:二分图,是图论中的一种特殊模型,设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且同一集合中不同的两点没有边相连。

这就是二分图。

 

举个栗子吧:

 

图论——二分图1:二分图以及判定

 

这是不是二分图?

反正我第一次看觉得不是

其实,是的,他是二分图,尽管看上去是连着的。

 

若我们将图中的一些边转一下,变成:

图论——二分图1:二分图以及判定

 

这就是一个明显的二分图。

集合A与B中的点互不相连。

 

因此,在手动判定二分图时学会转边!

 

辣魔,二分图要用计算机判定怎么实现?

 

数竞大佬:简单!

!!!染色大法!!!

 

图论——二分图1:二分图以及判定

 

有没有熟悉的感觉

 

0表示还未访问,1表示在集合A中,2表示在集合B中。

 

col(color)储存颜色。

初始化为0.

上代码:

 

 其实是模板

可以记忆。

 1 vector <int> v[N];
 2 void dfs(int x,int y){
 3   col[x]=y;            
 4   for (int i=0; i<v[x].size(); i++) {
 5      if (!col[v[x][i]]) dfs(v[x][i],3-y);
 6      if (col[v[x][i]]==col[x]) FLAG=true;      //产生了冲突
 7   }
 8 }
 9 for (i=1; i<=n; i++) col[i]=0;    //初始化
10 for (i=1; i<=n; i++) if (!col[i]) dfs(i,1);    //dfs染色
11 if (FLAG) cout<<"NO"; else cout<<"YES";

 

下一章我们将讲到二分图的匹配,我们明天见。

上一篇:Solaris zfs文件系统实例配置


下一篇:oracle数据库sql中文乱码问题,字符编码环境变量