最小.cpp

一个用c++实现的最小生成树的源代码

#include<iostream>
using namespace std;

int tag=1;
const int MaxNumEdge=50;
const int MaxNumVertices=20;

class MinSpanTree;
class Minheap;
class Gragh;


class MSTEdgeNode	
{
friend class MinSpanTree;
friend class Minheap;
friend class Gragh;
public:
   	MSTEdgeNode &operator =(MSTEdgeNode &s)
	{
		cost=s.cost;
		head=s.head;
		tail=s.tail;
		return *this;
	}

private:
	int tail, head;
	float cost;
};


class MinSpanTree
{
public:
	MinSpanTree(int sz=MaxNumEdge-1): MaxSize(sz), EdgeNum(0) 
	{
		edgevalue=new MSTEdgeNode[MaxSize];
	}
	
	void Insert(MSTEdgeNode  item)
	{
       edgevalue[EdgeNum]=item;
	   EdgeNum++;
	}
	void OutTheTree()
	{
		float sum=0;
		if(EdgeNum==0)
		{
			cout<<"最小树为 : "<<"  "<<0<<endl;
		}
		else
		{
			cout<<"最小生成树为:  ";
		    for(int i=0; i<EdgeNum; i++)
			{
     		   cout<<" < "<<edgevalue[i].tail<<" , "<<edgevalue[i].head<<" > "<<"  ";
			  sum+=edgevalue[i].cost;

			} 
		    cout<<endl;
		}
		cout<<endl;
		cout<<"权值为 : "<<"  "<<sum<<endl;
	}
protected:
	MSTEdgeNode *edgevalue;
	int MaxSize, EdgeNum;
};

const int DefaultSize=20;


class UFSets
{
private:
	int *perant;
	int size;
public:
	UFSets(int s)
	{		
		size=s;
		perant=new int[size+1];
        for(int i=0; i<size; i++)
	       	*(perant+i)=-1;
	}
	int Find(int i)
	{  

	  for(int j=i; perant[j]>=0; j=perant[j]);
         while(i!=j)
		{
			int temp=perant[i];
			perant[i]=j;
			i=temp;
		}
		return j;
				
	}
void Union(int Root1, int Root2)
{
	int temp=perant[Root1]+perant[Root2];
	if(perant[Root2]<perant[Root1])
	{
		perant[Root1]=Root2;
		perant[Root2]=temp;
	}
	else
	{
		perant[Root2]=Root1;
	   	perant[Root1]=temp;
	}
}

};


class Minheap
{
private:
	MSTEdgeNode *heap;
	int currentsize;
	int MaxheapSize;
public:
	Minheap(int maxsize)
	{
		heap=new MSTEdgeNode[maxsize];
		currentsize=0;
	}
	Minheap( MSTEdgeNode arr[], int n)
	{
		heap=new MSTEdgeNode[n];
		heap=arr; currentsize=n;
		int currentpos=(currentsize-2)/2;
		while(currentpos>=0 )
		{
             Filterdown(currentpos,currentsize-1);
			 currentpos--;
		}
	}
	void Filterdown(  int start, int Endofheap)
	{
        int i=start, j=2*i+1; 
		MSTEdgeNode temp=heap[i];
        while(j<Endofheap)
		{
			if(j<Endofheap&&heap[j].cost>heap[j+1].cost) j++;
			if(temp.cost<=heap[j].cost) break;
			else
			{
				heap[i]=heap[j];    
				i=j;
				j=2*j+1;
			}
		
		}
		heap[i]=temp;
	}
	void Filterup(int start)
	{
       int j=start, i=(j-1)/2;
	   MSTEdgeNode temp=heap[j];
	   while(j>0)
	   {
		   if(heap[i].cost<=temp.cost)  break;
		   else 
		   {
			   heap[j]=heap[i];  j=i;  i=(i-1)/2;
		   }
	   }
	   heap[j]=temp;
	}
    void Insert( MSTEdgeNode &x )
	{
		if(currentsize==MaxheapSize) {cerr<<"heap full"<<endl; }
		heap[currentsize]=x; Filterup(currentsize);
		currentsize++;
	}
    void  deleteMin( MSTEdgeNode &x )
	{
		x=heap[0]; 
		heap[0]=heap[currentsize-1];
		currentsize--;
		Filterdown(0, currentsize);
	}
};


class Gragh
{
private:
	int VerticesNum;
    float Edge[MaxNumVertices][MaxNumVertices];
	int CurrentEdges;

public:
	
	Gragh(int size)
	{
		for(int i=0; i<size; i++)
			for(int j=0;j<size; j++)
				Edge[i][j]=0;
		CurrentEdges=0;
		VerticesNum=size;
	}

	int NumberOfEdges()
	{
		return CurrentEdges;
	}

	void BuildGragh( )
	{
        int a[40];
		int k=0;
		cout<<"请输入图的邻接矩阵 :"<<endl;
		
		for(int i=0; i<VerticesNum; i++)
		{
			for(int j=0;j<VerticesNum; j++)
			{
				cin>>Edge[i][j];
				if(Edge[i][j]!=0&&Edge[i][j]>0)
				{
					CurrentEdges++;
					a[k]=i;
					a[k+1]=j;
					k=k+2;
				}
			}
		}
        for(int j=0; j<VerticesNum; j++)
		{
	        for(i=0; i<k; i++)
			{
				if(j==a[i])
				{
					tag=1; 
					break;
				}
                else 
				{
					tag=0;
				}
			}
		   if(tag==0)
		   {
	        	break;
		   }
		}
	}

	void Kruskal(MinSpanTree &T)
	{
       MSTEdgeNode e;
	   Minheap H(CurrentEdges);
	   int u, v;
	   UFSets F(VerticesNum);

	   for(u=0; u<VerticesNum; u++)
		   for(v=u+1; v<VerticesNum; v++)
			   if(Edge[u][v]>0)
			   {
				   e.tail=v; e.head=u;
				   e.cost=Edge[u][v];
				   H.Insert(e);
			   }

	  int count=1;
	  while(count<VerticesNum)
	  {
		  H.deleteMin(e);
          v=F.Find(e.tail);
		  u=F.Find(e.head);
		  if(u!=v)
		  {
			  F.Union(u,v);
			  T.Insert(e); 
			  count++;
		  }
	  }
	}
};


void main()
{
     cout<<endl;
	 cout<<"  **************    最小生成树算法   *****************"<<endl;
	 cout<<endl;
	 cout<<"           **********************************"<<endl;
     int vertice, sz=MaxNumEdge-1;

	 MinSpanTree T(sz);
	 cout<<"please Input the VerticesNum:"<<endl;
	 
     cin>>vertice;
     cout<<endl;
	 
	 Gragh G(vertice);
	 G.BuildGragh();
	 cout<<endl;

	 if(tag==0)
	 {
		 cout<<"请输入连通图!!! "<<endl;
	 }

	 else
	 {
	   G.Kruskal(T);
	   T.OutTheTree();	   
	 } 
	 cout<<endl;
}