kruskal.cpp

最小生成树的经典算法——Kruskal算法。用C++实现

#include<iostream.h>
#define Max 100000
struct edge
{
	int fromvex,endvex;
	float length;
	int group;
};
struct node
{
	int fromvex,endvex;
	float length;
	node *next;
};
node * insert(node * head,int i,int j,float length)
{
	node *p;
	node *q=NULL;
	node *N;
	p=head;
	if(!head)
	{
		head=new node;
		head->fromvex=i;head->endvex=j;
		head->length=length;head->next=NULL;
		return head;
	}
	while(p&&p->length<length)
	{
		q=p;
		p=p->next;
    }
	N=new node;
	N->fromvex=i;N->endvex=j;
	N->length=length;
	N->next=p;
	if(q==NULL)
		return N;
	else 
	{
		q->next=N;
		return head;
	}

//	if(p==head) return q;
 //   else return head;
}
node *Popstack(node *top,int& i,int& j,float &length)
{
	node *p;
	if(top==NULL)
	{
		cout<<"Under flow!"<<endl;
		return NULL;
    }
	else
	{
		i=top->fromvex;j=top->endvex;
		length=top->length;
		p=top;
		top=top->next;
		delete p;
		return top;
	}
}
main()
{
	float length;
	int n,i,j,k=0,m,In1=0,In2=0;
	edge *T;
	node *head=NULL;
	cout<<"输入顶点数目！"<<endl;
	cin>>n;
	T=new edge[n-1];
	cout<<"输入边信息，点，边权！权值输入-1 结束输入"<<endl;
	cin>>i;cin>>j;
	cin>>length;
	while(length!=-1)
	{
		head=insert(head,i,j,length);
		cout<<"输入边信息，点，边权！权值输入-1 结束输入"<<endl;
		cin>>i;cin>>j;
		cin>>length;
	}
while(k<n-1)
	{
		head=Popstack(head,i,j,length);
		In1=k+1;In2=k+2;
		for(m=0;m<k;m++)
		{
			if(T[m].fromvex==i||T[m].endvex==i)
				In1=T[m].group;
			if(T[m].fromvex==j||T[m].endvex==j)
				In2=T[m].group;
		}
		if(In1!=In2)
		{
			T[k].fromvex=i;T[k].endvex=j;
			T[k].length=length;
			T[k].group=In1;
			for(j=0;j<=k;j++)
			if(T[j].group==In2) 
				T[j].group=In1;
			k++;
		}
	}
	for(k=0;k<n-1;k++)
		cout<<T[k].fromvex<<","<<T[k].endvex<<","<<T[k].length<<endl;
return 0;
}