50分求助：怎样判断一个无向连通图是否为二分图？
请高手帮帮忙：
二部图（bipartite graph） G=（V，E）是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。
请用C编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。设G用二维数组A来表示，大小为n*n（n为结点个数）。
[解决办法]
我做了各深度优先遍历的算法，改了几个地方，可以判断是否为二分图，
时间复杂度为O（n×n）跟图的存储方式有关，希望对楼主有帮助^_^
#include <stdio.h>
#define N 6
#define MAX 100
int count = 0;/*访问顺序计数*/
int color[N] = {MAX,MAX,MAX,MAX,MAX,MAX};/*分别对图着两种颜色1,0*/
int factor = 0;/*控制着何种颜色*/
/*
*为结点途中节点i的所有邻节点设定颜色，如果冲突，则不是二分图
*/
void setColor(int g[N][N],int i)
{
int k;
for(k=0;k <N; k++)
{
/*对所有节点i的邻接节点*/
if((g[i][k] == 0) && (i != k))
{
if(color[k] == MAX)
{/*对未着色的邻居着色*/
color[k] = factor;
}
/*已经被着色而且与邻节点i颜色相同，不是二分图*/
if(color[k] == color[i])
{
printf( "该图不是二分图\n ");
exit(1);
}
}
}
}
/*
*深度优先遍历该图
*/
void dfs(int g[N][N],int i)
{
int k;
count++;
g[i][i] = count;
/*访问该顶点，这里对顶点颜色数组着色*/
if(color[i] == MAX)
{
color[i] = factor;
}
factor = (factor+1)%2;/*对邻节点换另外一种颜色*/
for(k=0;k <N; k++)
{
/*对所有节点i的邻接节点*/
if((g[i][k] == 0) && (i != k))
{
setColor(g,i);/*对所有相邻的结点着色*/
if(g[k][k] == 0)
/*访问没有被访问的邻节点*/
dfs(g,k);
}
}
}
void printGraph(int g[N][N])
{
int i,j;
for(i=0;i <N;i++)
{
for(j=0;j <N;j++)
if(g[i][j] == MAX)
printf( " , ");
else
printf( "%d, ",g[i][j]);
printf( "\n ");
}
}
void DFS(int g[N][N])
{
int i;
/*遍历图的所有连通分量*/
for(i=0;i <N;i++)
{
if(g[i][i] == 0)
/*遍历某个连通子图*/
dfs(g,0);
}
printf( "\n该图是二分图\n ");
}
main(void)
{
int G_YES[N][N]=
{/*二分图的例子，0 表示有连接，MAX表示无连接*/
0,MAX,MAX,0,0,MAX,
MAX,0,MAX,0,0,0,
MAX,MAX,0,0,MAX,0,
0,0,0,0,MAX,MAX,
0,0,MAX,MAX,0,MAX,
MAX,0,0,MAX,MAX,0
};
int G_NO[N][N]=
{/*非二分图的例子*/
0,MAX,0,0,0,MAX,
MAX,0,MAX,MAX,0,0,
0,MAX,0,0,MAX,0,
0,MAX,0,0,MAX,MAX,
0,0,MAX,MAX,0,0,
MAX,0,0,MAX,0,0
};
/*遍历前*/
printf( "遍历之前的图：\n ");
printGraph(G_YES);
/*遍历*/
DFS(G_YES);
/*遍历后*/
printf( "遍历之后的图：\n ");
printGraph(G_YES);
}
