kruskal算法.cpp

kruskal算法

#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);
}