prim最小生成树算法实验报告.doc

算法分析与设计之Prim学院:软件学院学号:9:吕吕一、问题描述Prim的定义Prim算法是贪心算法的一个实例,用于找出一个有权重连通图中的最小生成树,即:具有最小权重且连接到所有结点的树。(强调的是树,树是没有回路的)。实验目的选择一门编程语言,根据Prim算法实现最小生成树,并打印最小生成树权值。:假设G=(V,E)是连通的,TE是G上最小生成树中边的集合。算法从U={u0}(u0∈V)、TE={}开始。重复执行下列操作:在所有u∈U,v∈V-U的边(u,v)∈E中找一条权值最小的边(u0,v0)并入集合TE中,同时v0并入U,直到V=U为止。此时,TE中必有n-1条边,T=(V,TE)为G的最小生成树。Prim算法的核心:始终保持TE中的边集构成一棵生成树。,其时间复杂度为O(n^2),其时间复杂度与边得数目无关,N为顶点数,而看ruskal算法的时间复杂度为O(eloge)跟边的数目有关,适合稀疏图。三、数据结构的设计图采用类存储,定义如下:classGraph{private: int*VerticesList; int**Edge; intnumVertices; intnumEdges; intmaxVertices;public: Graph(); ~Graph(); boolinsertVertex(constintvertex); boolinsertEdge(intv1,intv2,intcost); intgetVertexPos(intvertex); intgetValue(inti); intgetWeight(intv1,intv2); intNumberOfVertices(); intNumberOfEdges(); voidPrim();}其中,图中结点连接情况及权值使用二重指针表示,即二维数组实现邻接矩阵。代码与运行结果代码运行结果:源码://普雷姆算法#include<iostream>usingnamespacestd;constintmaxWeight=10000;constintDefaultVertices=10000;constintmaxEdges=10000;constintMAXINT=10000000;classGraph{private: int*VerticesList; int**Edge; intnumVertices; intnumEdges; intmaxVertices;public: Graph(); ~Graph(); boolinsertVertex(constintvertex); boolinsertEdge(intv1,intv2,intcost); intgetVertexPos(intvertex); intgetValue(inti); intgetWeight(intv1,intv2); intNumberOfVertices(); intNumberOfEdges(); voidPrim(); voidlvlv(Graph&G);};istream&operator>>(istream&in,Graph&G);ostream&operator<<(ostream&out,G