#include

　　#include

　　#define MAXVEX 30

　　#define MAXCOST 1000

　　/*

　　每一步扫描数组lowcost，在V-U中找出离U最近的顶点，令其为k，并打印边(k,closest[k]), 然后修改lowcost和closest，标记k已经假如U。c表示图邻接矩阵，弱不存在边(i,j),则c[i][j]的值为一个大于任何权而小于无限打的阐述，这里用MAXCOST表示

　　*/

　　/*一直图的顶点为{1,2,...,n},c[i][j]为(i,j)的权，打印最小生成树的每条边*/

　　void prim (int c[MAXVEX][MAXVEX], int n)

　　{

　　int i,j,k,min,lowcost[MAXVEX],closest[MAXVEX];

　　for(i=2;i<=n;i++) /*从顶点1开始*/

　　{

　　lowcost[i]=c[1][i];

　　closest[i]=1;

　　}

　　closest[1]=0;

　　for(i=2;i<=n;i++) /*从U之外求离U中某一顶点最近的顶点*/

　　{

　　min=MAXCOST;

　　j=1;

　　k=i;

　　while(j<=n)

　　{

　　if(lowcost[j]

　　{

　　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]=c[k][j];

　　closest[j]=k;

　　}

　　}

　　}