mintree.cpp

数据结构最小生成树

#include "stdio.h" 
/*普里姆算法构造最小生成树*/
#define MAXVEX 30
#define MAXCOST 1000

void prim(int c[MAXVEX][MAXVEX],int n)
{
        int i,j,k,min,lowcost[MAXVEX],closest[MAXVEX];
        for(i=2;i<=n;i++)
        {
               lowcost[i]=c[1][i];
               closest[i]=1;
        }
        closest[1]=0;
        for(i=2;i<=n;i++)
        {
               min=MAXCOST;
               j=1;
               k=1;
               while(j<=n) 
               {
                      if(lowcost[j]<min&&closest[j]!=0)
                      {
                              min=lowcost[j];
                              k=j; 
                      }  
                      j++;
               }
               printf("(%d,%d)",closest[k],k);//输出生成树的边
               closest[k]=0; //第k顶点并入u集
               for(j=2;j<=n;j++)
                      if(closest[j]!=0&&c[k][j]<lowcost[j])//新顶点并入u集后重新选择最小边
                      {
                              lowcost[j]=c[k][j];
                              closest[j]=k; 
                      } 
        }              
}

void main()
{printf("==============================================================\n");
printf("                 键入1回车，求最小生成树\n");
printf("                 键入2回车，退出程序\n");
printf("==============================================================\n");

 
 
do{ int m;char nn;
 scanf("%d",&m);scanf("%c",&nn);
if(m==1){


        int n,k,i,j,e,mx[MAXVEX][MAXVEX];
        for(i=0;i<=n;i++)
              for(j=0;j<=n;j++)
                      mx[i][j]=MAXCOST; 
        
printf("输入图（如果图是无向图，请输入边数的2倍）的顶点数(n)，边数(e):");
scanf("%d,%d",&n,&e);
printf("请把各顶点用数字表示为：");
for(i=1;i<=n;i++)printf("%d ",i);
printf("\n\n");
printf("下面开始输入每条边的起点和终点，以及该边的权\n");
for(k=1;k<=e;k++) 
{  int m1=0,n1=0,l=0;
	printf("第%d条边=>",k);
     printf("   起点:");
     scanf("%d",&m1);        
       printf("  终点:");
	   scanf("%d",&n1);
printf("  权值:");
scanf("%d",&l);
mx[m1][n1]=l;
}      

printf("\n最小生成树边集:\n");
        prim(mx,n);  


printf("\n   完毕\n"); 
printf("==============================================================\n");
printf("                 键入1回车，求最小生成树\n");
printf("                 键入2回车，退出程序\n");
printf("==============================================================\n");
}

else if(m==2)break;
else printf("错误命令！请按说明重新输入\n");

}while(1);






}