最小代价生成树.cpp

数据结构中

#include<iostream.h>
enum Boolean{FALSE,TRUE};
class Graph{
private:int nmax;
int *length;Boolean *s; int *dist;int* pre;
public:Graph(int max)
	   {nmax=max;length=new int[nmax][nmax];s=new Boolean[nmax]; 
	   dist=new int[nmax];pre=new int[nmax];
	   }
	   void Embody()
	   {for(int i=0;i<nmax;i++)for(int j=0;j<nmax;j++)
	   {cout<<'('<<i<<','<<j<<')'<<':';cin>>length[i][j];
	   }
	   }
	   int choose(int n)
	   {int k=0;for(int i=0;i<n;i++)if(dist[i]<dist[k])k=i;return k;
	   }
	   void MCST(int n,int v)
	   {for(int i=0;i<n;i++)
	   {s[i]=FALSE;dist[i]=length[v][i];
	   }
	   s[v]=TRUE;dist[v]=0;
	   for(int i=0;i<n-1;i++)
	   {int u=choose(n);s[u]=TRUE;
	   for(int w=0;w<n;w++)if(!s[w])if(length[u][w]<dist[w]){pre[w]=u;dist[w]=length[u][w];}
	   }
	   };
void main(){int max;cin>>max; Graph G1(max);
	   G1.Embody();
	   G1.MCST(max,0);
	   }