Prim最小生成树算法实验报告
8页1、. . 算法分析与设计之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:in
2、t *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 = 10000
3、000;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=
《Prim最小生成树算法实验报告》由会员l****分享,可在线阅读,更多相关《Prim最小生成树算法实验报告》请在金锄头文库上搜索。
龙湖别墅项目方案解读
鸿达_天津城市广场商业城市综合体项目整体策划研究报告
黑弧奥美-保利西海岸XXXX年度推广
高宁哲学思维与领导艺术(北师大)
黄-文科班《综合探究聚焦文化竞争力》
食物中毒概述幻灯片ppt-欢迎各位领导、专家莅临指导
风险的测度、定价与绩效评估
香山·碧海晴空推广构想
项目管理培训_项目框架思维方法
项目管理石油大学
项目管理的应用-提升企业管理水平
项目十复合肥料与复混肥料生产
项目六车身测量
项目二 图根控制测量
项目八-PowerPoint演示文稿
电信天翼校园推广案
组织及组织工作
管理心理学主
项目05 导游人员的语言技能
管理心理学第7讲领导者心理
2024-04-17 27页
2024-04-17 6页
2024-04-17 9页
2024-04-17 36页
2024-04-17 16页
2024-04-17 18页
2024-04-17 45页
2024-04-17 7页
2024-04-17 38页
2024-04-17 28页