main.cpp

数据结构中的Prim算法 本人自己编的 望大家给与支持

#include<iostream.h>
typedef int vextype;
struct edgenode
{
	int adjvex;
	float length;
	edgenode *next;
};
struct vexnode
{
	vextype vertex;
	edgenode *link;
};
struct edge
{
	int fromvex,endvex;
	float length;
};
int n;
vexnode *Createtable()
{	
	int i,j;
	float length;
	edgenode *s;
	vexnode *graph;
	cout<<"输入图中结点个数！"<<endl;
	cin>>n;
	graph=new vexnode [n];
	for(i=0;i<n;i++)
	{
		graph[i].vertex=i+1;
		graph[i].link=NULL;
	}
	cout<<"输入点之间的联结信息 权为-1结束输入!"<<endl;
	cin>>i;
	cin>>j;
	cin>>length;
	while(length>-1)
	{
		s=new edgenode;
		s->adjvex=j;
		s->length=length;
		s->next=graph[i-1].link;
		graph[i-1].link=s;
		s=new edgenode;
		s->adjvex=i;
		s->next=graph[j-1].link;
		s->length=length;
		graph[j-1].link=s;
		cout<<"输入点之间的联结信息 权为-1结束输入!"<<endl;
		cin>>i;
		cin>>j;
		cin>>length;
		
	}
	return graph;
}
edgenode * search(edgenode  *p,int v)
{
	while(p)
	{
		if(p->adjvex==v)
			return p;
		else 
			p=p->next;
	}
	return NULL;
}

main()
{
	int k,j,m,v;
	float min,max=10000,length;
	vexnode *graph;
	edgenode *p;
	edge e,*T;
	graph=Createtable();
	T=new edge [n-1];
	
	for(j=0;j<n-1;j++)
	{
		p=graph[0].link;
		T[j].fromvex=1;
		T[j].endvex=j+2;
		if(p&&(p=search(p,j+2)))
		{	
			T[j].length=p->length;
		}
		else
			T[j].length=max;
	}
	for(k=0;k<n-1;k++)
	{
		min=max;
		for(j=k;j<n-1;j++)
			if(T[j].length<min)
			{
				min=T[j].length;
				m=j;
			}
		e=T[m];T[m]=T[k];T[k]=e;
		v=T[k].endvex;
		
		for(j=k+1;j<n-1;j++)
		{
			p=graph[v-1].link;
			if(p&&(p=search(p,T[j].endvex)))
				length=p->length;
			else
				length=max;
			if(length<T[j].length)
			{
				T[j].length=length;
				T[j].fromvex=v;
			}
		}
	}
	for(k=0;k<n-1;k++)
		cout<<T[k].fromvex<<","<<T[k].endvex<<","<<T[k].length<<endl;
	return 0;
}