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

算法分析与设计之Prim学院：软件学院 学号：201421031059 姓名：吕吕一、问题描述1. Prim的定义 Prim算法是贪心算法的一个实例，用于找出一个有权重连通图中的最小生成树，即：具有最小权重且连接到所有结点的树。(强调的是树，树是没有回路的)。2. 实验目的选择一门编程语言，根据Prim算法实现最小生成树，并打印最小生成树权值。二、 算法分析与设计1.Prim算法的实现过程 基本思想：假设G(V，E)是连通的，TE是G上最小生成树中边的集合。算法从Uu0（u0V）、TE开始。重复执行下列操作： 在所有uU，vVU的边(u，v)E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到VU为止。 此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。 Prim算法的核心:始终保持TE中的边集构成一棵生成树。2.时间复杂度Prim算法适合稠密图，其时间复杂度为O(n2)，其时间复杂度与边得数目无关，N为顶点数，而看ruskal算法的时间复杂度为O(eloge)跟边的数目有关，适合稀疏图。三、数据结构的设计图采用类存储，定义如下：class Graphprivate: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 using namespace std;const int maxWeight=10000;const int DefaultVertices=10000;const int maxEdges=10000;const int MAXINT = 10000000;class Graphprivate: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+)Edgei=new intmaxVertices;/邻接矩阵表示权值for(i=0;imaxVertices;i+)for(j=0;jmaxVertices;j+)Edgeij=(i=j)?0:maxWeight;Graph:Graph()delete VerticesList;delete Edge;/获取结点在结点数组中的下标，从0开始int Graph:getVertexPos(int vertex)for(int i=0;i=0&i-1&v1-1&v2(istream &in ,Graph &G)/边的范围是n-1至n(n-1)/2,n为顶点数int edges,vertices,i,j,k;int start,end,weight;/输入顶点 inverticesedges;for(i=1;i=vertices;i+)G.insertVertex(i);i=0;while(istartendweight;j=G.getVertexPos(start);k=G.getVertexPos(end);if(j=-1|k=-1)coutinput error!endl;elseG.insertEdge(j,k,weight);i+;return in;/输出图对象ostream& operator(ostream &out,Graph &G)int i,j,vertices,edges;int start,end,weight;vertices=G.NumberOfVertices();edges=G.NumberOfEdges();outvertices,edgesendl;for(i=0;ivertices;i+)for(j=i+1;j0 & weightmaxWeight)start=G.getValue(i);end=G.getValue(j);out(start,end,weight)endl;return out;/普雷姆算法void Graph:Prim () int *lowcost,*nearvex;int sum=0; lowcost=new intnumVertices; nearvex=new intnumVertices; for (int i=1;inumVertices;i+) lowcosti=Edge0i; /顶点0到各顶点的代价 nearvexi=0; /及最短带权路径 nearvex0=-1;/顶点0到生成树顶点集合int count = 0;/生成树边值数组存放指针for(int i=1;inumVertices;i+) /循环n-1次,加入n-1条边 int min=MAXINT; int v=0;for(int j=0;jnumVertices;j+)/顶点j不在最小生成树中且边权值比min小if (nearvexj!=-1 & lowcostjmin )v=j;/求生成树外顶点到生成树内顶点具有最小min=lowcostj;/权值的边, v是当前具最小权值的边的位置 /找到了下一个结点if(v!=0)/v=0表示再也找不到要求的顶点了count+; /向生成树边值数组内存放 sum+=lowcostv; nearvexv=-1;/作该边已加入生成树标记/更新权值for (int j=1;jnumVertices;j+)if (nearvexj!=-1 & Edgevjlowcostj ) /j不在生成树中 /需要修改lowcostj = Edgevj;nearvexj = v; int c=0; /coutsumendl;for(int k=1;knumVertices;k+)c+=lowcostk;coutcendl;int main()cout请输入图结点数，边数和权值，格式如下：endl;cout结点数