# 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);                        //輸出最小生成樹
		 }