目录
概述
判断二分图
算法实例
C++ 示例代码
概述
对于一个无向图 G=(V,E) ,它的顶点集 V 可以恰好分为两个不相交的子集,并且在这个无向图中,任意一条边所连接的两个顶点都分别属于这两个不同的子集,那么我们将这个无向图称作 二分图(如果你愿意也称 二部图)。
图例:(A中的点没有边直接相连,B同理)
判断二分图
我们可以使用 DFS 的方法对图进行染色,遍历所有点,如果当前点未被染色,则从此点开始进行 DFS 并进行染色,对路径上的点交替染色,如果发现在某个点时矛盾,原图就不为二分图。
时间复杂度为 O(N),空间复杂度为 O(N+E)。
算法实例接下来,用一个例子说明染色的过程
给定一张图
下面我们开始染色,节点 1 未被染色,我们从 1 开始进行 DFS。
先将 1 染成黄色(其他颜色也可以)。
我们发现 2 与 1 直接相连且未被染色,就继续搜索 2,染成蓝色。
我们发现 3 与 2 直接相连且未被染色,就继续搜索 3,染成黄色。
再没有与 3 相连的其他边了,所以我们回溯到 2 ,继续染 4 为黄色,类似 5 也是,最后全染完了就得到了二分图判断和分组结果。
那么,一个无向图在什么情况下不能成为一个二分图呢?
当无向图中不存在 奇环(结点个数为奇数的环)时,该图就可以成为二分图,反之就不能成为二分图。
例如这张图:
首先,我们把 1 染成黄色:
接下来,我们把与 1 相邻的 2,4 染成蓝色:
接下来,我们把与 2 相邻的 3 染成黄色:
这时我们发现,5 因为和 4 相邻,所以要被染成黄色;同时还和 3 相邻,所以要被染成蓝色。因此,这个图不能称为一个二分图。
C++ 示例代码为了便于理解,我们令二分图的两组分别染成颜色 1 和颜色 2 ,未染色的点的颜色标记为 0。
//时间复杂度:O(m+n) //二分图判定:当且仅当一个图中不含奇数环 //此算法可以判定二分图:黑->白->黑->白…… #include#include #include #define _for(i,a,b) for (int i=(a);i<=(b);i++) using namespace std; const int N=1e5+5,M=2e5+10;//N是点的上限,M是边的 int h[N],e[M],ne[M],idx;//单链表 int color[N];//染成i色的点 void init(){ idx=0; memset(h,-1,sizeof(h)); } 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(){ init(); int n,m; scanf("%d%d",&n,&m); while (m--){ int a,b; scanf("%d%d",&a,&b); add(a,b),add(b,a); } _for(i,1,n){ if (!color[i]){ if (!dfs(i,1)){ puts("No"); return 0; } } } puts("Yes"); return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)