thesmallest tree.cpp

数据结构 生成最小数的求解方法 根据严蔚敏的c版本的数据结构里的课后实验求的

/*
#include<iostream>
#include <algorithm>
using namespace std;

#define MAX_Vex_Num 30                            //图的最大顶点数;
#define MAX 100                                          //图的最大边数；
/////////////kruskal算法//////////////////////////
//边的信息结点；
typedef struct
{
int begin;                                      //边的起始顶点；
int end;                                         //边的终止顶点；
int value;                                      //边的权值；
}edge,E[MAX];
bool compair1(edge a,edge b)
{
return a.value<b.value;
}
int readedge(edge E[],int n)               //输入图中边的信息;
{
char a,b;
int m,i,j;
int k=0;
for(i=1;i<n;i++)                  //读入每条边的信息;
{        
   cin>>a>>m;
   for(j=1;j<=m;j++)
   {
   
    cin>>b;
    E[k].begin=a-'A';
    E[k].end=b-'A';
    cin>>E[k].value;
    k++;      
   }
  
}
return k;
}

//kruskal算法；
int kruskal(edge E[],int vexnum,int edgenum)       //vexnum为顶点数,edgenum为边数;
{
int i,j,m1,m2,sn1,sn2,k;
int vset[MAX_Vex_Num];
int sum=0;
for(i=0;i<vexnum;i++)              //初始化辅助数组；
   vset[i]=i;
k=1;                       //表示当前构造最小生成树的第几条边，初值为1；
j=0;                       //表示E中边的下标，初值为1；
while(k<vexnum)             //生成的边数小于n时循环；
{
   m1=E[j].begin;              //取一条边的起始顶点；
   m2=E[j].end;                //取一条边的终止顶点；
  
   sn1=vset[m1];               //分别得到两个顶点所属集合的编号；
   sn2=vset[m2];
  
   if(sn1!=sn2)                //两顶点属于不同的集合，该边是最小生成树的边；
   {
    sum+=E[j].value;
    k++;                 //生成边数增1；
    for(i=1;i<=vexnum;i++)          //两个集合统一编号；
     if(vset[i]==sn2)             //集合编号为sn2的改为sn1；
      vset[i]=sn1;
   }
   j++;                        //扫描下一条边；
}
return sum;
}

int main()
{
edge E[MAX];
int edgenum;
int vexnum;
     while(cin>>vexnum)
{
if(vexnum==0)break;
edgenum=readedge(E,vexnum);                    //该图的边的数目；
sort(E,E+edgenum,compair1);
     int sum=kruskal(E,vexnum,edgenum);
cout<<sum<<endl;
}
return 0;
}

*/

/*
#include <stdio.h>
#define MAX 100
#define INF 32767

void prim(int cost[][MAX],int ver,int v)
{
    int i,j,k;
    int min;
    int lowcost[MAX][2];
    for(i=0;i<ver;i++)
    {
        lowcost[i][1]=v;   //这里是指这条边是由谁为起点的
        lowcost[i][0]=cost[v][i];        //这是这条边的权值
        if(i==v)
            lowcost[i][1]=-1;
    }
    for(i=0;i<ver-1;i++)
    {
        min=INF;

        for(j=0;j<ver;j++)
        {
        
            if(lowcost[j][1]!=-1&&lowcost[j][0]<min&&lowcost[j][0]!=0)  //寻找最小权值可用的边
           {
                min=lowcost[j][0];
                k=j;
            }
        }
        printf("%d---->%d cost %d ",lowcost[k][1],k,min);
        lowcost[k][1]=-1;
        for(j=0;j<ver;j++)   //修改 lowcost 把新加进来的点的更短的边替换原来的边
        {
            if(lowcost[j][1]!=-1&&(lowcost[j][0]>cost[k][j]&&cost[k][j]!=0||lowcost[j][0]==0))
          {
                lowcost[j][0]=cost[k][j];
                lowcost[j][1]=k;
            }
        }
    }
}

void Kruskal(int cost[][MAX],int ver,int v)
{
    int edge[MAX][3];
    int vset[MAX];
    int i,j,k;
    int a,b,c,t;
    int min;
    //这里用最简单的快排来 实际可以用更快的排序
    k=-1;
    for(i=0;i<ver;i++)
    {
        vset[i]=i;
        for(j=i;j<ver;j++)
       {
            if(cost[i][j]!=0)
            {
                k++;
                edge[k][0]=i;
                edge[k][1]=j;
                edge[k][2]=cost[i][j];
            }
        }
    }
    
    for(i=0;i<k;i++)
    {
        min=edge[i][2];
        t=i;
        for(j=i+1;j<k;j++)
       {
            if(edge[j][2]<min)
            {
                t=j;
                min=edge[j][2];
            }
        }
        if(t!=i)
       {
            a=edge[i][0];b=edge[i][1];c=edge[i][2];
            edge[i][0]=edge[t][0];edge[i][1]=edge[t][1];edge[i][2]=edge[t][2];
            edge[t][0]=a;edge[t][1]=b;edge[t][2]=c;
        }
    }
   // 到这里都是为了排序 其实可以用更好的方法来写 

    k=1;
    i=0;
    while(i<ver)
    {
        if(vset[edge[i][0]]!=vset[edge[i][1]])   //vset为集合 这里不同的边选出来后会有不同的集合
        {
            printf("%d-->%d cost is %d ",edge[i][0],edge[i][1],edge[i][2]);
            for(j=0;j<ver;j++)
                if(vset[j]==vset[edge[i][1]])
                    vset[j]=vset[edge[i][0]];        
            k++;
        }
        i++;
    }
}

int main()
{
    int cost[MAX][MAX];
    int i,j;
    int a,b,c;
    int ver,arc;
    for(i=0;i<MAX;i++)
        for(j=0;j<MAX;j++)
            cost[i][j]=0;
    printf("input the ver and arc ");
    scanf("%d %d",&ver,&arc);
    for(i=0;i<arc;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        cost[a][b]=c;
        cost[b][a]=c;
    }
    for(i=0;i<ver;i++)
    {
        for(j=0;j<ver;j++)
            printf("%d",cost[i][j]);
        printf(" ");
    }
    prim(cost,ver,0);
    Kruskal(cost,ver,0);
    return 0;
}
*/