Kruskal_suanfa.rar_Kruskal算法

#include<iostream> #include<string> #include"SeqList.H" #include"UFSet.H" #include"MinHeap.H" using namespace std; const int MaxNumEdge=50; const int MaxNumVertices=10; class MinSpanTree; template <class NameType,class DistType> class Graph { public: Graph(int sz); void Kruscal(MinSpanTree &T); // private: SeqList<NameType> VerticesList; DistType Edge[MaxNumVertices][MaxNumVertices]; int CurrrentEdge; }; const float MAXNUM=12345; // class MSEdgeNode { friend class MinSpanTree; //private: public: int tail,head; float cost; }; // class MinSpanTree { public: MinSpanTree(int sz=MaxNumEdge-1):MaxSize(sz),n(0) {edgevalue=new MSEdgeNode[MaxSize];} int Insert(MSEdgeNode &item); protected: MSEdgeNode *edgevalue; int MaxSize ,n; }; // template <class NameType,class DistType> void Graph <NameType, DistType> ::Kruscal(MinSpanTree &T) { MSEdgeNode e; MinHeap<MSEdgeNode> H(CurrrentEdge); int NumVertices=VerticesList.MaxSize,u,v; cout<<NumVertices; /* UFSets F(NumVertices); F.Print(); for(u=0;u<NumVertices;u++) for(v=u+1;v<NumVertices;v++) if(Edge[u][v]!=MAXNUM){ e.tail=u;e.head;e.cost=Edge[u][v];H.Insert(e); } int count=1; while(count<NumVertices) { H.RemoveMin(e); u=F.Find(e.tail);v=F.Find(e.head); if(u!=v){ F.Union(u,v);//T.Insert; count++; } } */ } // template <class NameType,class DistType> Graph <NameType, DistType> ::Graph(int sz) { CurrrentEdge=0;int Vertices; cout<<"输入结点个数"<<endl; cin>>Vertices; SeqList<NameType> VerticesList(Vertices); cout<<VerticesList.MaxSize; cout<<"输入结点"<<endl; for (int a=0;a<Vertices;a++) { NameType x; cin>>x; VerticesList.Insert(x); } cout<<"输入边数"<<endl; cin>>sz; cout<<"输入边："<<endl; for (int i=0;i<sz;i++) { cout<<"**"<<endl; for(int j=0;j<sz;j++) { cin>>Edge[i][j]; if( Edge[i][j]!=0) CurrrentEdge++; } } } main() { MinSpanTree T; Graph<string,float> a(9); a.Kruscal(T); }