prim 算法实现

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define INF 1000000
#define MAX 200
int n,m,v;
int edge[MAX][MAX];
int lowcast[MAX];
int nextvex[MAX];
void prim(int U0)
{
	int i,j;
	int sum=0;
	for(i=1;i<=n;i++)
	{
		lowcast[i]=edge[U0][i];
		nextvex[i]=U0;
	//	printf("edge[1][%d]=%d,nextvex[%d]=%d\n",i,lowcast[i],i,nextvex[i]);
	}
	nextvex[U0]=-1;
	for(i=1;i<n;i++)
	{
		int min=INF;
		int v=-1;
		for(j=1;j<=n;j++)
			if(nextvex[j]!=-1 && lowcast[j]<min)
			{
				v=j;
				min=lowcast[j];
			//	printf("v=%d,min=%d\n",v,min);

			}

			//	printf("v=%d,min=%d\n",v,min);
	
	if(v!=-1)
	{
		printf("%d %d %d\n",nextvex[v],v,lowcast[v]);
		nextvex[v]=-1;
		sum+=lowcast[v];
		for(j=1;j<=n;j++)
		{
			if(nextvex[j]!=-1 && edge[v][j]<lowcast[j])
			{
				lowcast[j]=edge[v][j];
				nextvex[j]=v;
//				printf("lowcast=%d\n",lowcast[j]);
			}
		}
	}
	}
	printf("sum of MST is %d\n",sum);
}
int main()
{
	//freopen("in.txt","r",stdin);
	int i,j;
	int u,v,w;
	scanf("%d%d",&m,&n);
	memset(edge,0,sizeof(edge));
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		edge[u][v]=edge[v][u]=w;

	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(i==j)
				edge[i][j]=0;
			else if(edge[i][j]==0)
				edge[i][j]=INF;
		}
	}
	prim(1);
	
	return 0;
}

以下是测试数据:

7 9
1 2 28
1 6 10
2 3 16
2 7 14
3 4 12
4 5 22

4 7 18
5 6 25
5 7 24

结果运行如下:

prim 算法实现

原文：http://blog.csdn.net/yuzibo747/article/details/19127725