Prim最小生成树算法实验报告材料.doc

《Prim最小生成树算法实验报告材料.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计之Prim学院：软件学院学号：201421031059：吕吕一、问题描述1.Prim的定义Prim算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。2.实验目的选择一门编程语言，根据Prim算法实现最小生成树，并打印最小生成树权值。二、算法分析与设计1.Prim算法的实现过程基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作：在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE

2、中，同时v0并入U，直到V＝U为止。此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。Prim算法的核心:始终保持TE中的边集构成一棵生成树。2.时间复杂度Prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，N为顶点数，而看ruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。三、数据结构的设计图采用类存储，定义如下：classGraph{private:int*VerticesList;int**Edge;intnumVertices;intnumEdges;intmaxVertices;public:Graph();~Graph(

3、);boolinsertVertex(constintvertex);boolinsertEdge(intv1,intv2,intcost);intgetVertexPos(intvertex);intgetValue(inti);intgetWeight(intv1,intv2);intNumberOfVertices();intNumberOfEdges();voidPrim();}其中，图中结点连接情况及权值使用二重指针表示，即二维数组实现邻接矩阵。四、代码与运行结果代码运行结果：源码：//普雷姆算法#includeusingnamespacestd;constint

4、maxWeight=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)

5、;intgetValue(inti);intgetWeight(intv1,intv2);intNumberOfVertices();intNumberOfEdges();voidPrim();voidlvlv(Graph&G);};istream&operator>>(istream&in,Graph&G);ostream&operator<<(ostream&out,Graph&G);//默认构造函数Graph::Graph(){maxVertices=DefaultVertices;numVertices=0;numEdges=0;inti,j;VerticesList=newint[m

6、axVertices];Edge=(int**)newint*[maxVertices];for(i=0;i

7、or(inti=0;i=0&&i<=numVertices)?VerticesList[i]:NULL;};intGraph::getWeight(intv1,intv2){return(v1!