Prim最小生成树算法实验报告
. . 算法分析与设计之Prim学院：软件学院 学号：9 ：吕吕一、问题描述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 <iostream>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;i<maxVertices;i+)Edgei=new intmaxVertices;/邻接矩阵表示权值for(i=0;i<maxVertices;i+)for(j=0;j<maxVertices;j+)Edgeij=(i=j)?0:maxWeight;Graph:Graph()delete VerticesList;delete Edge;/获取结点在结点数组中的下标，从0开始int Graph:getVertexPos(int vertex)for(int i=0;i<numVertices;i+)if(VerticesListi=vertex)return i;return -1;/共有属性int Graph:getValue(int i)return (i>=0&&i<=numVertices)?VerticesListi:NULL;int Graph:getWeight(int v1,int v2)return (v1!=-1&&v2!=-1)?Edgev1v2:0;int Graph:NumberOfVertices()return numVertices;int Graph:NumberOfEdges()return numEdges;/插入结点bool Graph:insertVertex(const int vertex)if(numVertices=maxVertices)return false;VerticesListnumVertices+=vertex;return true;/插入边，v1和v2为结点在数组的下标bool Graph:insertEdge(int v1,int v2,int cost)if(v1>-1&&v1<numVertices&&v2>-1&&v2<numVertices&&Edgev1v2=maxWeight)Edgev1v2=Edgev2v1=cost;numEdges+;return true;elsereturn false;/输入图信息istream& operator>>(istream &in ,Graph &G)/边的围是n-1至n(n-1)/2,n为顶点数int edges,vertices,i,j,k;int start,end,weight;/输入顶点 in>>vertices>>edges;for(i=1;i<=vertices;i+)G.insertVertex(i);i=0;while(i<edges)in>>start>>end>>weight;j=G.getVertexPos(start);k=G.getVertexPos(end);if(j=-1|k=-1)cout<<"input 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();out<<vertices<<","<<edges<<endl;for(i=0;i<vertices;i+)for(j=i+1;j<vertices;j+)weight=G.getWeight(i,j);if(weight>0 && weight<maxWeight)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;i<numVertices;i+) lowcosti=Edge0i; /顶点0到各顶点的代价 nearvexi=0; /及最短带权路径 nearvex0=-1;/顶点0到生成树顶点集合int count = 0;/生成树边值数组存放指针for(int i=1;i<numVertices;i+) /循环n-1次,加入n-1条边 int min=MAXINT; int v=0;for(int j=0;j<numVertices;j+)/顶点j不在最小生成树中且边<0,j>权值比min小if (nearvexj!=-1 && lowcostj<min )v=j;/求生成树外顶点到生成树顶点具有最小min=lowcostj;/权值的边, v是当前具最小权值的边的位置 /找到了下一个结点if(v!=0)/v=0表示再也找不到要求的顶点了count+; /向生成树边值数组存放 sum+=lowcostv; nearvexv=-1;/作该边已加入生成树标记/更新权值for (int j=1;j<numVertices;j+)if (nearvexj!=-1 && Edgevj<lowcostj ) /j不在生成树中 /需要修改lowcostj = Edgevj;nearvexj = v;
