prim.cpp

c++下的AOV实现

#include<iostream.h>
#define MaxNum 32767
const int MaxNumVertices=10;
template<class Type> class Graph{
	private:
		Type Edge[MaxNumVertices][MaxNumVertices];
		int CurrentVertices,CurrentEdges;
	public:
		Graph(){
			for(int i=0;i<MaxNumVertices;i++)
				for(int j=0;j<MaxNumVertices;j++)
					Edge[i][j]=MaxNum;
		}
		void InsertEdge(int v1,int v2,Type weight){
			Edge[v1][v2]=Edge[v2][v1]=weight;
		}		
		friend istream& operator>>(istream& in,Graph<Type>& G){
			int v1,v2,i;
			Type weight;
			char c1,c2;
			cout<<"输入顶点数:";
			in>>G.CurrentVertices;
			cout<<"输入边数以示结束:";
			in>>G.CurrentEdges;
			cout<<"逐个输入边,输入格式(如 0,1,28):"<<endl;
			for(i=0;i<G.CurrentEdges;i++)
			{
				in>>v1>>c1>>v2>>c2>>weight;
				G.InsertEdge(v1,v2,weight);
			}
			return in;
		}
        void prim(){
			Type* lowcost=new Type[CurrentVertices];
			int* nearvex=new int[CurrentVertices];
			for(int i=0;i<CurrentVertices;i++){
				lowcost[i]=Edge[0][i];nearvex[i]=0;
			}
			nearvex[0]=-1;
			for(i=1;i<CurrentVertices;i++){
				Type min=MaxNum;int v=0;
				for(int j=0;j<CurrentVertices;j++)
					if(nearvex[j]!=-1&&lowcost[j]<min){v=j;min=lowcost[j];}
					if(v){
						cout<<"("<<nearvex[v]<<","<<v<<")";
						nearvex[v]=-1;
						for(j=1;j<CurrentVertices;j++)
							if(nearvex[j]!=-1&&Edge[v][j]<lowcost[j])
							{lowcost[j]=Edge[v][j];nearvex[j]=v;}
					}
			}
			cout<<endl;
		}		
};
void main(){
	Graph<int> a;
	cin>>a;
	a.prim();
}