最小生成树prim.cpp

贪心算法解一系列算法经典问题

//? 最小生成树Prim算法

#include <stdio.h>
#define INFINITY 1000
#define MAXN 10

typedef struct
{
	int vnum;
	int arcs[MAXN][MAXN];
} graph;

void creat_graph(graph *p)
{
	int i,j,n,v1,v2,w;
	printf("vertex's number: ");
	scanf("%d",&n);
	p->vnum=n;
	for(i=0; i<n; ++i)
		for(j=0; j<n; ++j)
			if(i==j) p->arcs[i][j]=0;
			else p->arcs[i][j]=INFINITY;
	printf("Input edge=vertex1,vertex2,weight\n  (The End of Input\"-1,-1,0\"):\n");
	i=1;
	do
	{
		printf("edge%d = V1,V2,W%d = ",i,i++);
		scanf("%d,%d,%d",&v1,&v2,&w);
		if(v1>=0 && v1<n && v2>=0 && v2<n)
		{
			p->arcs[v1][v2]=w;
			p->arcs[v2][v1]=w;
		}
	} while(!(v1==-1 && v2==-1));
}

int prim(graph G,int v, int tree[][3])
{
	int i,j,k,p,min,c;
	int lowcost[MAXN],closest[MAXN];
	for(i=0; i<G.vnum; ++i)
	{
		closest[i]=v;
		lowcost[i]=G.arcs[v][i];
	}
	c=p=0;
	for(i=0; i<G.vnum-1; ++i)
	{
		min=INFINITY;
		for(j=0; j<G.vnum; ++j)
			if(lowcost[j]!=0&&lowcost[j]<min)
			{
				min=lowcost[j];
				k=j;
			}
		tree[p][0]=closest[k];
		tree[p][1]=k;
		tree[p][2]=min;
		p++;
		c+=min;
		lowcost[k]=0;
		for(j=0; j<G.vnum; ++j)
			if(G.arcs[k][j]!=0&&G.arcs[k][j]<lowcost[j])
			{
				lowcost[j]=G.arcs[k][j];
				closest[j]=k;
			}
	}
	return c;
}

void main()
{
	int i;
	int tree[MAXN][3];
	int cost;
	graph G;
	creat_graph(&G);
	cost=prim(G,1,tree);
	printf("Minimum-cost spanning tree(prim):\n");
	printf("edge\tweight\t\n");
	for(i=0; i<G.vnum-1; ++i)
		printf("v%d-v%d\t%d\n",tree[i][0],tree[i][1],tree[i][2]);
	printf("Cost:\t%d\n",cost);
}