二分图(Bipartite Graph)

二分图的定义

假设S=(V,E)是一个无向图。如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),就可以称图S为一个二分图。简单来说,就是顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。

Bipartite Graph -- from Wolfram MathWorld

二分图的定理:

二分图不存在奇环(长度为奇数的环)。
因为每一条边都 是从一个集合走到另一个集合,只有走偶数次才可能回到同一个集合。

二分图的判断

       对于二分图的判断方法最常见的是染色法,就是对每一个点进行染色操作,只用两种颜色标注,能不能使所有的点都染上了色且相邻两个点的颜色不同?如果可以那么这个图就是一个二分图,如果产生冲突则不是二分图。对于判断是否是一个二分图的方法可以用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;
}
Scroll to Top