prim.cpp

本程序是用来prim算法用C++的完全实现,可供大家学习使用.

#include <iostream.h>
#include "head.h"

void prim(AdjList G)
{
	int i,j,min,y;
	ArcNode *p,*s;
	int N[n+1],C[n+1];
	AdjList T;
	point status[n+1];      //相当于X,Y两个集合的布尔向量
	for(i=1;i<=n;i++)       //初使化T
	{
		T[i].num=i;
		T[i].firstarc=NULL;
		T[i].tailarc=NULL;
	}
	for(i=1;i<=n;i++)      //初使化C,使C[i]=∞
	{
		C[i]=100000000;
	}
	status[1].x=1;status[1].y=0;  //初使化点的状态,分在X,Y两个集合中
	for(i=2;i<=n;i++)
	{
		status[i].x=0;
		status[i].y=1;
	}
	for(p=G[1].firstarc;p!=NULL;p=p->nextarc)
	{
		N[p->num]=1;
		C[p->num]=p->data;
	}
	for(j=1;j<=n-1;j++)
	{
		min=100000000;y=0;
		for(i=1;i<=n;i++)       //令y∈Y,使得C[y]最小
		{
			if(status[i].y==1)
			{
				if(min>C[i])
				{
					min=C[i];
					y=i;
				}
			}
		}
		//将边(y,N[y]加入T

		//将N[y]插入y的邻接表中
		s=new ArcNode;
		s->num=N[y];
		s->data=C[y];
		if(T[y].firstarc==NULL)
		{
			T[y].firstarc=s;
			T[y].tailarc=s;
		}
		else
		{
			T[y].tailarc->nextarc=s;
			T[y].tailarc=s;
		}
		T[y].tailarc->nextarc=NULL;
		//将y插入N[y]的邻接表中
		p=new ArcNode;
		p->num=y;
		p->data=C[y];
		if(T[N[y]].firstarc==NULL)
		{
			T[N[y]].firstarc=p;
			T[N[y]].tailarc=p;
		}
		else
		{
			T[N[y]].tailarc->nextarc=p;
			T[N[y]].tailarc=p;
		}
		T[N[y]].tailarc->nextarc=NULL;
		//将顶点y加入X,并从Y中删除
		status[y].x=1;
		status[y].y=0;
		for(p=G[y].firstarc;p!=G[y].tailarc->nextarc;p=p->nextarc)
		{
			if(p->data<C[p->num])
			{
				N[p->num]=y;
				C[p->num]=p->data;
			}
		}
	}
	//输出生成树T的邻接表	
/*	cout<<"最小生成树的邻接表为:"<<'\n';
	for(i=1;i<=n;i++)
	{
		p=T[i].firstarc;
		cout<<i<<"->";
		while(p!=NULL)
		{
			cout<<p->num<<"["<<p->data<<"]"<<"->";
			p=p->nextarc;
		}
		cout<<"NULL"<<endl;
	}
*/
	for(i=1;i<=n;i++)
	{
		while(T[i].firstarc!=NULL)
		{
			p=T[i].firstarc;
			T[i].firstarc=p->nextarc;
			delete p;
		}
	}
}