prim.cpp

掌握Prim算法的特点

         # include<stdio.h>
         # define inf 9999
         # define max 40
         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-U集的最小边
					 if((lowcost[j]<min)&&(lowcost[j]!=0))//当lowcost[j]<min，且边对应的顶点j不是U集中的顶点
					 {
						 min=lowcost[j];
						 k=j;
					 }
					 printf("(%d,%d)%d\t",closest[k],k,min);
					 lowcost[k]=0;              //顶点k加入到U集标志
					 for(j=2;j<=n;j++)
						 if(g[k][j]<lowcost[j]) //修改由顶点k到其它顶点边的权值
						 {
							 lowcost[j]=g[k][j];
						     closest[j]=k;
						 }
				 printf("\n");
			 }
		 }
		 int adjg(int g[][max])                  //建立无向图
		 {
			 int n,i,j,v1,v2,weight;
			 printf("total n=");
			 scanf("%d",&n);                     //输入图中顶点的个数
			 for(i=1;i<=n;i++)                  //将矩阵中全部元素的初值设为无限大
				 for(j=1;j<=n;j++)
					 g[i][j]=inf;
				 do
				 {
					 printf("v1,v2,weight=");
					 scanf("%d %d %d",&v1,&v2,&weight);//如果不存在v1-v2的边，则输入“9999”
					 g[v1][v2]=weight;
					 g[v2][v1]=weight;
				 }while(v1!=0&&v2!=0&&weight!=0);
				 return(n);
		 }
		 void prg(int g[][max],int n)          //输出无向图的邻接矩阵
		 {
			 int i,j;
			 for(i=0;i<=n;i++)
				 printf("%d\t",i);
			 for(i=1;i<=n;i++)
			 {
				 printf("\n%d\t",i);
				 for(j=1;j<=n;j++)
					 printf((g[i][j]==inf)?"\t":"%d\t",g[i][j]);
			 }
			 printf("\n");
		 }
		 void main()
		 {
			 int g[max][max],n;
			 n=adjg(g);                        //建立无向图
			 printf("Matrix of the undirectde graph:\n");
			 prg(g,n);                         //输出无向图的邻接矩阵
			 printf("Edges of minicost spanning tree:\n");
			 prim(g,n);                        //输出最小生成树
		 }