prim.cpp

数据结构中的最小生成树实现

#include<stdio.h>
#define MAX 300

struct 
{
	int x;
	int lowcost;
}closedge[MAX];

int getmin(int n) //找出当前边权值最小的点
{ 
	int i,min=999999,vex=-1;
	for(i=0;i<n;i++)
		if(closedge[i].lowcost!=0 && closedge[i].lowcost<min)
		{
			min=closedge[i].lowcost;
			vex=i;
		}
		return vex; 
}

void prim(int Graph[MAX][MAX],int u,int n)
{//用prim算法从第u个顶点出发构造最小生成树，输出选择的顶点和权值
	//记录从顶点U到V-U的代价最小的边的辅助数组closedge[]
	int i,j,k,t,sum_cost=0;;
	k=u;
	for(j=0;j<n;j++) //辅助数组初始化
		if(j!=k) 
		{
			closedge[j].x=u;
			closedge[j].lowcost=Graph[k][j];
		}
		closedge[k].lowcost=0;//开始的点先加入到U中
		for(i=1;i<n;i++)//做n-1次，因为要n-1条边
		{
			k=getmin(n);
			if(k == -1)
				break;
			sum_cost+=closedge[k].lowcost;
			closedge[k].lowcost=0;//把第K顶点点加入U中
			for(j=0;j<n;j++)        //新顶点加入U后重新选择最小边
				if(Graph[k][j]<closedge[j].lowcost)
				{
					closedge[j].x=k;
					closedge[j].lowcost=Graph[k][j];
				}
		}
	//	printf("sum_cost=%d\n",sum_cost);
}

main()
{
	int Graph[MAX][MAX],i,j,n;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			scanf("%d",&Graph[i][j]);
    prim(Graph,0,n);
}