文章目录

一、二分图定义二、二分图判定三、代码实现

一、二分图定义

二分图，是图论中的一种特殊模型，设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且同一集合中不同的两点没有边相连。看一个例子： 图中点集合分为A(包含2，4号顶点)和B(包含1，3，5，6号顶点)，并且A,B集合中的点没有形成连接关系，显然这是一个二分图。

二、二分图判定

定理1：无向图G为二分图的一个充要条件是： 1、G中至少包含两个顶点 2、G中所有的回路长度都必须是偶数 也就是说，一个图是二分图的充分必要条件是这个图不包含长度为奇数的圈。

那么，怎么实现呢？ 很简单，采用染色的方法，对于一个无向图，起初图中所有顶点都是无色，我们从任意未染色顶点出发，对这个顶点进行染色，对于与这个顶点相邻的的顶点，有三种情况： 1、未染色 那么将这个顶点染色，染与当前顶点不相同的颜色。 2、已经染色但是当前顶点颜色不同 那么跳过该顶点 3、已经染色但是与当前顶点相同。则该图不是一个二分图，返回失败。 图中所有顶点已经进行染色，并且没有出现相邻顶点颜色相同的情况，则该图是一个二分图。

三、代码实现

1、DFS实现思想也就是上面二分图判定所描述的。

/*描述:给定一个无向图，判断是否是二分图*/

/*思想:通过dfs染色的方法，从任意未遍历过的顶点出发进行染色,如果有与当前顶点染色相同的，则不是二分图

否则继续搜索与当前顶点相连的未染色的节点，并且染上相反的颜色，最后遍历完所有的顶点，相邻顶点没有同色，则为二分图。

时间复杂度O(n^2),空间复杂度O(n^2),若采用邻接表作为存储结构，则时间复杂度为O(n+m)

*/

#include

using namespace std;

const int maxn=1005;

int edge[maxn][maxn];//邻接矩阵存储

int color[maxn];//标记顶点颜色

int n,m;

bool dfs(int u,int c)

{

color[u]=c;//对u点进行染色

for(int i=1;i<=n;i++)//遍历与u点相连的点

{

if(edge[u][i]==1)//如果i点与u点相连

{

if(color[i]==c) return false;//i点的染色重复，则不是二分图

if(!color[i]&&!dfs(i,-c)) return false;//该点未染色，染上相反的颜色.dfs继续搜索

}

}

return true;//所有点染色完成之后，并且相邻顶点没有同色，则为二分图

}

int main()

{

while(scanf("%d%d",&n,&m)!=EOF)

{

memset(edge,0,sizeof(edge));

memset(color,0,sizeof(color));

for(int i=0;i

{

int u,v;

scanf("%d%d",&u,&v);

edge[u][v]=1;//无向图，因此uv和vu都需要

edge[v][u]=1;

}

bool flag=false; //默认为二分图

for(int i=1;i<=n;i++)

{

if(!color[i])

{

if(!dfs(i,1))

{

printf("No\n");

flag=true;

}

}

}

if(!flag) printf("Yes\n");

}

return 0;

}

/*

测试数据:

4 3

1 4

2 3

3 4 Yes

6 8

1 2

1 3

2 4

3 4

3 5

3 6

4 6

5 6 No

*/

2、BFS思想主要是遍历这个图中每一层的时候，检查每一层是否有圈，有圈则不是二分图。

#include

using namespace std;

const int maxn=1005;

int color[maxn];

vectoredge[maxn];//存储采用vector，相当于邻接表

int n,m;

bool bfs(int x,int c)

{

queueq;

q.push(x);//从x号节点开始

color[x]=c;

while(!q.empty())

{

int now=q.front();

q.pop();

for(int i=0;i

{

int v=edge[now][i];

if(color[v]==0)//若v点未进行染色

{

color[v]=-color[now];//将v点染色，并且不与当前节点now节点相同

q.push(v);//将v点放进队列继续访问

}

if(color[v]==color[now]) return false;//与当前节点颜色相同，该图不是二分图

}

}

return true;

}

int main()

{

while(~scanf("%d%d",&n,&m))

{

memset(color,0,sizeof(color));

for(int i=1;i<=m;i++)

{

int u,v;

scanf("%d%d",&u,&v);

edge[u].push_back(v);

edge[v].push_back(u);

}

bool flag=true;

for(int i=1;i<=n;i++)

{

if(color[i]==0&&!bfs(i,1))

{

flag=false;

break;

}

}

if(flag) printf("The Graph is two partite graph!\n");

else printf("The Graph is not two partite graph!\n");

}

}

3、文件读写方式代码，采用fstream的两个子类ifstream和ofstream。

#include

using namespace std;

const int maxn=1005;

int color[maxn];

vectoredge[maxn];

int n,m;

int bfs(int x,int c)

{

queueq;

q.push(x);

color[x]=c;

while(!q.empty())

{

int now=q.front();

q.pop();

for(int i=0;i

{

int j=edge[now][i];

if(color[j]==0)

{

color[j]=-color[now];

q.push(j);

}

if(color[j]==color[now]) return false;

}

}

return true;

}

int main()

{

ifstream in("C:\\Users\\Administrator\\Desktop\\input.txt");

ofstream out("C:\\Users\\Administrator\\Desktop\\output.txt");

if(!in.is_open()) cout<<"open file input.txt failure"<

if(!out.is_open()) cout<<"open file output.txt failure"<

while(!in.eof())

{

memset(color,0,sizeof(color));

in>>n>>m;

if(in.fail()) break;//解决ifstream和ofstream文件尾读取两次问题

for(int i=0;i

{

int u,v;

in>>u>>v;

edge[u].push_back(v);

edge[v].push_back(u);

}

bool flag=true;

for(int i=1;i<=n;i++)

{

if(color[i]==0&&!bfs(i,1))

{

flag=false;

break;

}

}

if(flag) out<<"YES"<

else out<<"NO"<

}

in.close();

out.close();

return 0;

}

4、并查集实现二分图判定 思想：对于一条边的两个点将其与他们都不认识的人，也就是没有连接的点合并在同一个集合中，如果一条边两个点查找到的根节点一样，也就是说这两个节点已经在同一个集合中，说明这个图不是二分图。 代码：

#include

using namespace std;

const int maxn=1005;

int father[maxn];

int findset(int x)//并查集路径压缩

{

if(x!=father[x]) father[x]=findset(father[x]);

return father[x];

}

int main()

{

int n,m;

while(~scanf("%d%d",&n,&m))

{

for(int i=1;i<=2*n;i++) father[i]=i;

bool flag=true;

for(int i=1;i<=m;i++)

{

int u,v;

scanf("%d%d",&u,&v);

int fa=findset(u);//查找根节点

int fb=findset(v);

int x=findset(u+n);//查找u不认识的人的根节点

int y=findset(v+n);

if(fa==fb) flag=false;

else//将两个不认识的人合并在同一个集合中

{

father[x]=fb;

father[y]=fa;

}

}

if(flag) printf("YES\n");

else printf("NO\n");

}

return 0;

}

关于ifstream和ofstream参考：C++ifstream和ofstream的详细用法 关于二分图的匹配问题以及实现下面这篇文章中有详细介绍：二分图算法 关于并查集学习链接：并查集学习