实现最小代价生成树.cpp

数据结构中

#include<iostream.h>
template<class Type>
struct Element{int key;Type t;};
struct edge {int v1;int v2;};
template<class Type>
class MinHeap{private:Element<Type>*heap;
int n; int MaxSize;
public:
	MinHeap(int sz){MaxSize=sz;heap=new Element<Type>[MaxSize];n=0;}
	void Insert(Element<Type>x){
		if(n==MaxSize){cout<<"can't insert.\n";return;}
		n++;
		for(int i=n;1;){
			if(i==1)break;
			if(x.key>=heap[i/2].key)break;
			heap[i]=heap[i/2];i/=2;}heap[i]=x;
	}
	Element<Type>*Delete(Element<Type>&x){
		if(!n){cout<<"can't delete.\n";return 0;}
		x=heap[1];Element<Type>k=heap[n];n--;
		for(int i=1,j=2;j<=n;){
			if(j<n)if(heap[j].key>heap[j+1].key)j++;
			if(k.key<=heap[j].key)break;
			heap[i]=heap[j];i=j;j*=2;}
		heap[i]=k;return &x;
	}
};
class Sets{
private:int n;int *parent;
public:Sets(int sz){n=sz;parent=new int [sz];
	   for(int i=0;i<n;i++)parent[i]=-1;}
	   void WeightedUnion(int i,int j){
		   int temp=parent[i]+parent[j];
		   if(parent[i]<parent[j]){
			   parent[i]=j;parent[j]=temp;}
		   else{parent[j]=i;parent[i]=temp;}
	   }
	   int CollapsingFind(int i){
		   for(int r=i;parent[r]>=0;r=parent[r]);
		   while(i!=r){int s=parent[i];parent[i]=r;i=s;}return r;
	   }
};
void main(){
	Element<edge>x;cout<<"请输入堆的最大容量：";int max;cin>>max;
	MinHeap<edge>h(max);cout<<"请依次输入边的长度和顶点：";
	cin>>x.key;
	while(x.key>=0){cin>>x.t.v1>>x.t.v2;h.Insert(x);cin>>x.key;}
	cout<<"请输入顶点数：";
int n;cin>>n;Sets s1(n);edge*store=new edge[n-1];
int i=0;
while(i<n-1&&h.Delete(x)){
	int c1,c2;c1=s1.CollapsingFind(x.t.v1);
	c2=s1.CollapsingFind(x.t.v2);
	if(c1!=c2){s1.WeightedUnion(c1,c2);store[i++]=x.t;}
}
if(i==n-1){ cout<<"a minimum cost spanning tree has been found:";             
for(int i2=0;i2<n-1;i2++)cout<<'('<<store[i2].v1<<','<<store[i2].v2<<')';
cout<<endl;}
else cout<<"there is no minimum cost spanning tree.\n";
}