Prim最小生成树算法实验报告.docx

算法分析与设计之Prim学院：软件学院 学号：201421031059 姓名：吕吕一、问题描述Prim的定义 Prim算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。实验目的选择一门编程语言，根据Prim算法实现最小生成树，并打印最小生成树权值。算法分析与设计1.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中的边集构成一棵生成树。2.时间复杂度Prim算法适合稠密图，其时间复杂度为O(n^2)，其时间复杂度与边得数目无关，N为顶点数，而看ruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。三、数据结构的设计图采用类存储，定义如下：class Graph{private:int *VerticesList;int **Edge;int numVertices;int numEdges;int maxVertices;public:Graph();~Graph();bool insertVertex(const int vertex);bool insertEdge(int v1,int v2,int cost);int getVertexPos(int vertex);int getValue(int i);int getWeight(int v1,int v2);int NumberOfVertices();int NumberOfEdges();void Prim();}其中，图中结点连接情况及权值使用二重指针表示，即二维数组实现邻接矩阵。代码与运行结果代码运行结果：源码：//普雷姆算法#include iostreamusing namespace std;const int maxWeight=10000;const int DefaultVertices=10000;const int maxEdges=10000;const int MAXINT =class Graph{private:int *VerticesList;int **Edge;int numVertices;int numEdges;int maxVertices;public:Graph();~Graph();bool insertVertex(const int vertex);bool insertEdge(int v1,int v2,int cost);int getVertexPos(int vertex);int getValue(int i);int getWeight(int v1,int v2);int NumberOfVertices();int NumberOfEdges();void Prim();void lvlv(Graph G);};istream operator(istream in,Graph G);ostream operator(ostream out,Graph G);//默认构造函数Graph::Graph(){maxVertices=DefaultVertices;numVertices=0;numEdges=0;int i,j;VerticesList=new int [maxVertices];Edge=(int **)new int *[maxVertices];for(i=0;imaxVertices;i++)Edge[i]=new int[maxVertices];//邻接矩阵表示权值for(i=0;imaxVertices;i++)for(j=0;jmaxVertices;j++)Edge[i][j]=(i==j)?0:maxWeight;};Graph::~Graph(){delete []VerticesList;delete []Edge;};//获取结点在结点数组中的下标，从0开始int Graph::getVertexPos(int vertex){for(int i=0;inumVertices;i++)if(VerticesList[i]==vertex)return i;return -1;};//共有属性int Graph::getValue(int i){return (i=0i=numVertices)?Ve