二分图匹配的判定

布满荆棘的人生 2022-05-19 05:43 216阅读 0赞

**二分图：**

二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

简单的说，一个图被分成了两部分，相同的部分没有边，那这个图就是二分图，二分图是特殊的图。

即A或B中集合元素互不相干，不能出现A中元素与B中元素有关系还和资深元素有关系

那么我们如何判断一个图是不是二分图呢？

*  从其中一个定点开始，将跟它邻接的点染成与其不同的颜色，最后如果邻接的点有相同颜色，则说明不是二分图，每次用bfs遍历即可。
 *  代码：
    
        #include<queue>
        #include<cstdio>
        #include<cstring>
        #include<cstdlib>
        #include<cstring>
        #include<algorithm>
        using namespace std;
        int e[100][100];//建立一个邻接矩阵
        int color[100];//颜色标记法
        int n,m;//n个点，m个配对
        int bfs(int x)
        {
            queue<int>Q;
            color[x]=1;//染色
            Q.push(x);
            while(!Q.empty())
            {
                int now=Q.front();
                Q.pop();
                for(int i=1; i<=n; i++)
                {
                    if(color[i]==-1&&e[now][i]) //如果从now到i的边存且i点未着色
                    {
                        Q.push(i);//将i点压入队列
                        color[i]=!color[now];//将i点染成不一样的颜色
                    }
                    if(color[i]==color[now]&&e[now][i])//如果从now到i的边存在且i点和now点这一对邻接点颜色相同，则不是二分图   
                    {
                        return 0;
                    }
                }
            }
            return 1;//x点和所有点的关系搜完，且将邻接点染上颜色，如果没有相同颜色则返回真
        }
        int main()
        {
            int i,j,u,v;
            scanf("%d%d",&n,&m);
            memset(e,0,sizeof(e));
            memset(color,-1,sizeof(color));
            for(i=0; i<m; i++)
            {
                scanf("%d%d",&u,&v);
                e[u][v]=e[v][u]=1;
            }
            int flag=0;
            for(i=1; i<=n; i++)//搜索每个点
            {
                if(color[i]==-1&&!bfs(i)) //每次找没有着色的点进行判断，如果从它开始BFS发现相同色邻接点则不是二分图
                {
                    flag=1;
                    break;
                }
            }
            if(flag)
                printf("No\n");
            else
                printf("Yes\n");
            return 0;
        }