图论算法-最小生成树

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

/*
N是图的顶点数 
G[1 << 10][1 << 10]代表图的邻接矩阵，G[i][j] = 1,表示i和j连接，否则不连接
q[1 << 10]是BFS使用的队列
dis[1 << 10]是每个顶点到顶点0的最短距离 
head表示队头，t是队尾 
*/
 
int G[1 << 10][1 << 10],q[1 << 10],dis[1 << 10],head,h,t,N;

int BIPARTITE()/*在BFS的基础上稍作修改，从顶点编号0开始广搜,是二部图返回1,否则返回0*/
{
 int i,j;
 memset(dis,-1,sizeof(dis));/*初始化顶点未访问 */
 dis[0] = 0;
 head = h = t = 0;
 while(t <= h)
 {
  for(i = t;i <= h;i++)
   for(j = 0;j < N;j++)
   {
    if(G[q[i]][j]) 
    {
     if(j == q[i]) /*排除自环*/ 
      continue;
     if(dis[j] != -1 && (dis[q[i]] - dis[j]) % 2 == 0) /*说明顶点q[i]和顶点j连接会有奇环产生，不是二部图 */