最小生成树问题的算法实现及复杂度分析—天津大学计算.docx

算法设计与分析课程设计报告学院计算机科学与技术专业计算机科学与技术年级2011姓名XXX学号2013年5月19日题目:最小生成树问题的算法实现及复杂度分析摘要:该程序操作简单,具有一定的应用性。数据结构是计算机科学的算法理论基础和软件设计的技术基础,在计算机领域中有着举足轻重的作用,是计算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法,最小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛,如邮递员送信、公路造价等问题。本设计以VisualStudio2010作为开发平台,C/C++语言作为编程语言,以邻接矩阵作为存储结构,编程实现了最小生成树算法。构造最小生成树有很多算法,本文主要介绍了图的概念、图的遍历,并分析了PRIM经典算法的算法思想,最后用这种经典算法实现了最小生成树的生成。引言:假设要在n个城市之间建立通信联络网,则连接n个城市只需要n-1条线路。这时,自然会考虑这样一个问题,如何在节省费用的前提下建立这个通信网?自然在每两个城市之间都可以设置一条线路,而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n(n-1)/2条线路,那么如何在这些可能的线路中选择n-1条使总的代价最小呢?可以用连通网来表示n个城市以及n个城市之间可能设置的通信线路,其中网的顶点表示城市,边表示两个城市之间的线路,赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树,每一个生成树都可以是一个通信网。现在要选择这样一棵生成树,也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树(简称最小生成树)的问题。最小生成树是指在所有生成树中,边上权值之和最小的生成树,另外最小生成树也可能是多个,他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。正文普里姆(Prim)算法思想普里姆算法则从另一个角度构造连通网的最小生成树。它的基本思想是:首先选取图中任意一个顶点v作为生成树的根,之后继续往生成树中添加顶点w,则在顶点w和顶点v之间必须有边,且该边上的权值应在所有和v相邻接的边中属最小。在一般情况下,假设图G=(V,E)中已落在生成树上的顶点集为U,则尚未落在生成树上的顶点集为V-U,则从(V-U)顶点集中选取加入生成树的顶点w应满足下列条件:它和生成树上的顶点之间的边上的权值是在联接这两类顶点的所有边中权值属最小。从上述生成树的构造过程中回还可以发现一点,即每个顶点都是通过"一条边"加入到生成树上的,因此对集合V-U中的每个顶点,当它和集合U中的顶点有一条以上的边相连时,只需要保留一条权值最小的边即可。由此,在普里姆算法中需要附设一个辅助数组closedge,以记录从集合U到集合V-U中每个顶点当前的权值最小边。普里姆算法构造最小生成树的过程普里姆(Prim)算法设计:一:定义模块:、新类型及固定值定义。本程序可接受的最大顶点数为20个,没有连接的点之间,用100表示其权值。#include<iostream>usingnamespacestd;#defineMAX_VERTEX_NUM20//最大顶点数#defineQM100//最大值#defineOK1#defineERROR0intvisited[MAX_VERTEX_NUM];typedefintVertexType;typedefintVRType;,即定义类型。本程序采用的图定义是无向图的定义方式,存储模块采用邻接矩阵,便于查找。typedefintVertexType;typedefintVRType;ell//邻接矩阵的值{intadj;}ell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,um;//图的当前顶点数和弧数}MGraph;,定义辅助数组,进行判断遍历。typedefstruct{VertexTypeadjvex;VRTypelowcost;}closedge[MAX_VERTEX_NUM];,采用辅助数组进行结果的记录。typedefstruct{VertexTypehead;VRTypelast;intweight;}result[MAX_VERTEX_NUM];二:实现模块(函数),因为顶点的值和数组位置的下标不一定相等,所以加入顶点查找函数,返回顶点的值,便于结果显示、区分指针与内容,使思路更为清晰。intLocateVex(MGraph&G,Vertex