数据结构之实现Kruskal算法，求连通图的最小生成树

#include <iostream>
#include <algorithm>


using namespace std;


const int INF=99;


const int n=6;  //顶点数


int G[n][n]={INF,  6,  1,  5,INF,INF,
               6,INF,  5,INF,  3,INF,
               1,  5,INF,  5,  6,  4,
               5,INF,  5,INF,INF,  2,
             INF,  3,  6,INF,INF,  6,
             INF,INF,  4,  2,  6,INF,
            };


struct Edge
{
int Head;
int Tail;
int lowcost;
};


Edge E[n*n];  
int  Vexset[n];


inline bool cmp(const Edge &e1,const Edge &e2)
{
    return e1.lowcost < e2.lowcost;
}


int init()
{
    int e=0;
    for(int i=0;i<n;i++)
    {
        Vexset[i]=i;
for(int j=i+1;j<n;j++)  //矩阵上三角 
        {
            if(G[i][j]<INF)
            {
E[e].Head   =i;
                E[e].Tail   =j;
                E[e].lowcost=G[i][j];
                e++;
            }
        }  
    }
    sort(E,E+e,cmp);
return e;    
}


void kruskal()
{
int e=init();
for(int i=0;i<e;i++)  //遍历边 
{
int vs1=Vexset[E[i].Head];
int vs2=Vexset[E[i].Tail];

if(vs1!=vs2)      //边的两个顶点在不同的连通分量上，不形成回路 
{
   cout<<"v"<<E[i].Head+1<<" ";
cout<<"v"<<E[i].Tail+1<<"   ";
cout<<E[i].lowcost<<endl;

   for(int j=0;j<n;j++)
{
       if(Vexset[j]==vs2) Vexset[j]=vs1;  //合并vs1和vs2连同分量 
}
}
}
}


int main()
{
kruskal();
    
    return 0;
}