#include<iostream.h>

#define MAX_Vex_Num 30                           //圖的最大頂點數;
#define MAX 100                                         //圖的最大邊數；
/////////////kruskal算法//////////////////////////
//邊的信息結點；
typedef struct
{
   int begin;                                     //邊的起始頂點；
   int end;                                        //邊的終止頂點；
   float value;                                     //邊的權值；
}edge,E[MAX];

void readedge(edge E[],int edgenum)              //輸入圖中邊的信息;
{
   for(int i=1;i<=edgenum;i++)                 //讀入每條邊的信息;
   {
        
    cout<<" 起始頂點\n";
    cin>>E[i].begin;                           //起始頂點；
    cout<<"終止頂點\n";
       cin>>E[i].end;                              //終止頂點；
    cout<<" 權值\n";
       cin>>E[i].value;                           //權值；
   }
}
//對儲存邊信息的線性表遞增排序;
void orderlist(edge E[],int edgenum)       
{

cout<<"Edge's information\n";
   readedge(E,edgenum);                         //讀入邊信息；

   for(int i=1;i<=edgenum;i++)                 //用冒泡法對各邊的權值由小到大排序；
   {
          for(int j=1;j<edgenum-i+1;j++)
          {
                 if(E[j].value>E[j+1].value)      //前一結點較大時交換兩條邊的所有信息；
                 {
                        edge t;
                        t=E[j];
                        E[j]=E[j+1];
                        E[j+1]=t;
                 }
          }
   }
}

//kruskal算法；
void kruskal(edge E[],int vexnum,int edgenum)      //vexnum為頂點數,edgenum為邊數;
{
   int i,j,sn1,sn2,k,m1,m2;float sum=0;
   int vset[MAX_Vex_Num];

   for(i=1;i<=vexnum;i++)             //初始化輔助數組；
          vset[i]=i;
   k=1;                      //表示當前構造最小生成樹的第幾條邊，初值為1；
   j=1;                      //表示E中邊的下標，初值為1；
   while(k<vexnum)            //生成的邊數小于n時循環；
   {
          m1=E[j].begin;             //取一條邊的起始頂點；
          m2=E[j].end;               //取一條邊的終止頂點；

          sn1=vset[m1];              //分別得到兩個頂點所屬集合的編號；
          sn2=vset[m2];

          if(sn1!=sn2)               //兩頂點屬于不同的集合，該邊是最小生成樹的邊；
          {
                 cout<<"("<<m1<<","<<m2<<"):"<<E[j].value<<endl;
				 sum+=E[j].value;
		         cout<<"sum="<<sum<<endl;
                 k++;                //生成邊數增1；
                 for(i=1;i<=vexnum;i++)         //兩個集合統一編號；
                        if(vset[i]==sn2)            //集合編號為sn2的改為sn1；
                               vset[i]=sn1;
          }
          j++;                       //掃描下一條邊；
   }
}

void main()
{
   edge E[MAX];
   int edgenum;
   int vexnum;
   cout<<"該圖的邊的數目\n";
   cin>>edgenum;                   //該圖的邊的數目；
   cout<<"該圖的頂點數目\n";
   cin>>vexnum;                    //該圖的頂點數目；
   orderlist(E,edgenum);

   cout<<"The final tree is \n";
   kruskal(E,vexnum,edgenum);
}