prim.txt

数据结构中用普里姆(Prim)算法构造最小生成树

#include <stdio.h>

#define inf 9999

#define max 40

void prim(int g[][max],int n)

{int lowcost[max],closest[max];

 int i,j,k,min;

 for(i=2;i<=n;i++)                       //n个顶点，n-1条边

 {lowcost[i]=g[1][i];                   //初始化

  closest[i]=1;                            //顶点未加入到最小生成树中

 }

 lowcost[1]=0;                          //标志顶点1加入U集合

 for(i=2;i<=n;i++)                      //形成n-1条边的生成树

 {min=inf;

  k=0;

  for(j=2;j<=n;j++)           //寻找满足边的一个顶点在U,另一个顶点在V的最小边

         if((lowcost[j]<min)&&(lowcost[j]!=0))

         {min=lowcost[j];

          k=j;

         }

  printf("(%d,%d)%d ",closest[k],k,min);

  lowcost[k]=0;                          //顶点k加入U

  for(j=2;j<=n;j++)                     //修改由顶点k到其他顶点边的权值

         if(g[k][j]<lowcost[j])

         {lowcost[j]=g[k][j];

         closest[j]=k;

         }

         printf("
");

 }

}

int adjg(int g[][max])                  //建立无向图

{int n,e,i,j,k,v1,v2,weight;

 printf("输入顶点个数：");

 scanf("%d,%d",&n,&e);

 for(i=1;i<=n;i++)                       

        for(j=1;j<=n;j++)

               g[i][j]=inf;                   //初始化矩阵,全部元素设为无穷大 

 for(k=1;k<=e;k++)

 {printf("输入第%d条边的起点，终点，权值:",k);

  scanf("%d,%d,%d",&v1,&v2,&weight);

  g[v1][v2]=weight;

  g[v2][v1]=weight;

 }

 return(n);

}

void prg(int g[][max],int n)           //输出无向图的邻接矩阵

{int i,j;

 for(i=0;i<=n;i++)

        printf("%d ",i);

 for(i=1;i<=n;i++)

 {printf("
%d ",i);

 for(j=1;j<=n;j++)

        printf((g[i][j]==inf)?" ":"%d ",g[i][j]);

}

printf("
");

}

void main()

{int g[max][max],n;

n=adjg(g);

printf("输入无向图的邻接矩阵:
");

prg(g,n);

printf("最小生成树的构造:
");

prim(g,n);

}