二分图(Bipartite Graph)
二分图的定义
假设S=(V,E)是一个无向图。如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，就可以称图S为一个二分图。简单来说，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。
二分图的定理：
二分图不存在奇环(长度为奇数的环)。
因为每一条边都 是从一个集合走到另一个集合，只有走偶数次才可能回到同一个集合。
二分图的判断
对于二分图的判断方法最常见的是染色法，就是对每一个点进行染色操作，只用两种颜色标注，能不能使所有的点都染上了色且相邻两个点的颜色不同？如果可以那么这个图就是一个二分图，如果产生冲突则不是二分图。对于判断是否是一个二分图的方法可以用DFS和BFS两种方式去实现。
代码实现(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 | #include <iostream> #include <queue> using namespace std; //判断G图是否二分图，是返回true，否返回false bool isBipartite(int g[4][4],int src){ //创建一个colorArr数据，初始化，存结点的颜色。 int colorArr[4]; for (int i = 0; i <4; i++)colorArr[i]=-1; //给第一个结点着色 colorArr[src]=1; //创建一个队列，存广度搜索BFS时候的结点 queue<int> q; q.push(src); //while循环，从队列里把每个结点标记 while(!q.empty()){ //从队列将结点出队 int u=q.front(); q.pop(); //如果结点出现自己指向自己的边，返回false if(g[u][u]==1) return false; //遍历所有u的相接结点 for (int i = 0; i <4; i++){ //如果u与i有边相连接，并且i的颜色没有标注 if(g[u][i]&&colorArr[i]==-1){ //标注颜色为0 colorArr[i]=1-colorArr[u]; //把u的相接结点压到队列里 q.push(i); } //如果相邻结点颜色一样，说明不是二分图 else if(g[u][i]&&colorArr[u]==colorArr[i]) return false; } } //如果程序到这里，说明相邻结点没有颜色相撞的情况，是二分图 return true; } int main(){ int G[4][4] = { {0, 1, 0, 1}, {1, 0, 1, 0}, {0, 1, 0, 1}, {1, 0, 1, 0} }; if(isBipartite(G,0))cout<<"YES"; else cout<<"NO"; return 0; } |
习题：关押罪犯 [NOIP2010 提高组T3] [P1525][P1855]
Quizzes