prim.cpp

prim算法

#include<stdio.h>//带权无向连通图的最小生成树。
#include<stdlib.h>
#define LEN sizeof(struct node)
#define NULL 0
#define max 32767
struct node {int k,w;struct node *next;}*gr[101];
struct sttype{int v,d,p;}q[101];
int n,root,tot;
int qpos[101];
int hs;
void insert(int u,int v,int w)
{
	struct node *p;
	p=(struct node *)malloc(LEN);
	(*p).k=v;
	(*p).w=w;
	(*p).next=gr[u];
	gr[u]=p;
}
void swap(int a,int b)
{
	int i;
	struct sttype t;
	t.v=q[a].v;
	t.d=q[a].d;
	t.p=q[a].p;
	q[a].v=q[b].v;
	q[a].d=q[b].d;
	q[a].p=q[b].p;
	q[b].v=t.v;
	q[b].d=t.d;
	q[b].p=t.p;
	i=qpos[q[a].v];
	qpos[q[a].v]=qpos[q[b].v];
	qpos[q[b].v]=i;
}
void heapfy(int i)
{
	int m;
	m=i;
	do
	{
		i=m;
		if(2*i<=hs&&q[i*2].d<q[m].d)m=2*i;
		if(i*2+1<=hs&&q[i*2+1].d<q[m].d)m=2*i+1;
		if(i!=m)swap(i,m);
	}while(i!=m);
}
void decrease(int v,int k)
{
	q[v].d=k;
	while(v!=1&&q[v].d<q[v/2].d)
	{
		swap(v,v/2);
		v=v/2;
	}
}
void main()
{
    int i,u,v,m,w;
	struct node *p;
	scanf("%d%d",&n,&root);
	for(i=1;i<=n;i++)
		gr[i]=NULL;
    scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
        insert(u,v,w);
		insert(v,u,w);
	}
    tot=0;
    for(i=1;i<=n;i++)
	{
		q[i].v=i;
		q[i].d=max;
		qpos[i]=i;
	}
	q[root].d=0;
	q[root].p=0;
	swap(1,root);
	hs=n;
	while(hs>0)
	{
		u=q[1].v;
		if(u!=root)
		printf("%d--%d  %d ",q[1].p,u,q[1].d);
		tot=tot+q[1].d;
		swap(1,hs);
		hs--;
		heapfy(1);
		p=gr[u];
		while(p!=NULL)
		{
			v=qpos[(*p).k];
			if(v<=hs&&(*p).w<q[v].d)
			{
				q[v].p=u;
				decrease(v,(*p).w);
			}
			p=(*p).next;
		}
	}
	printf("\ntot=%d\n",tot);
}