最小生成树问题的算法实现及复杂度分析

1、算法设计与分析课程设计报告学 院计算机科学与技术专 业计算机科学与技术年 级姓 名 XXX学 号2013年5月19日题目：一心I :最小生成树问题的算法实现及复杂度分析 摘要：该程序操作简单，具有一定的应用性。数据结构是计算机科学的算 法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计 算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法，最 小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛，如邮 递员送信、公路造价等问题。本设计以Visual Studio 2010作为开发平台，C/C+ 语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小

2、生成树算法。构 造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了 PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。引言：丁 口：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1 条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通 信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的 经济代价。n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可 能的线路中选择n-1条使总的代价最小呢？可以用连通网来表示n个城市以及 n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之 间

3、的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多 不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树， 也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小 生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树， 另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就 是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。正文普里姆(Prim )算法思想普里姆算法则从另一个角度构造连通网的最小生成树。它的基本思想是： 首先选取图中任意一个顶点V作为生成树的根，之后继续往生成树中添加顶点 w，则在

4、顶点w和顶点V之间必须有边，且该边上的权值应在所有和V相邻接 的边中属最小。在一般情况下，假设图G=(V,E)中已落在生成树上的顶点集为 U，则尚未落在生成树上的顶点集为V-U，则从(V-U)顶点集中选取加入生成树 的顶点w应满足下列条件：它和生成树上的顶点之间的边上的权值是在联接这 两类顶点的所有边中权值属最小。从上述生成树的构造过程中回还可以发现一点，即每个顶点都是通过一 条边加入到生成树上的，因此对集合V-U中的每个顶点，当它和集合U中的 顶点有一条以上的边相连时，只需要保留一条权值最小的边即可。由此，在普里 姆算法中需要附设一个辅助数组closedge，以记录从集合U到集合V-U中每

5、个顶点当前的权值最小边。WS普里姆算法构造最小生成树的过程普里姆(Prim)算法设计：一：定义模块：头文件、新类型及固定值定义。本程序可接受的最大顶点数为20个，没有连 接的点之间，用100表示其权值。#includeusing namespace std;#define MAX_VERTEX_NUM 20dj=QM;cout输出网的个顶点(限数字)：endl;for(i=0;ii;cout建立弧，请输入条弧的顶点和权值 (v1,v2,w):endl;for(k=0;kv1v2weight;i=LocateVex(G,v1);j=LocateVex(G,v2);if(i0|j0)return

6、ERROR;j.adj=weight;ji.adj=ij.adj;return OK;1.最小生成树建立主程序，采用借助辅助数组的方式，对于辅助的数组，以 邻接表的选择点加入该数组，然后查找数组中权值最小，且未被选中的顶 点，然后返回该边，加入最小生成树中。void MiniSpanTree_PRIM(MGraph G,VertexType u)(closedge dge;owcost=kj.adj;djvex=u;owcost=0;djvex k endl;ead=dgek.adjvex;paxtime.last=k;x=LocateVex(G,dgek.adjvex);y=LocateVe

7、x(G,k);paxtime.weight=xy.adj;time+;dgek.lowcost=0;djdgej.lowcost)(owcost=kj.adj;dgej.adjvex=k;eadpaxtime.last paxtime.weightendl;辅助生成最小生成树的函数。int minimun(MGraph G,closedge F)(int i,min;for(i=0;i;i+)if(Fi.lowcost!=0) break;min=i;for(i=0;i;i+)if(Fi.lowcost!=0 &Fi.lowcostFmin.lowcost) min=i;return min;

8、数组的样式:jLowcostadjvex过程如下表：顶点标号都比图中的小1，比如v1为0，v2为1，这里首先选 择v1点。j012345Lowcost0423100100adjvex111111从这个表格可以看到依附到v1顶点的v3的Lowcost最小为2,那么选择v3， 选择了之后我们必须要更新Lowcost数组的值，因为记录从U到VU具有最小 代价的边，加入之后就会改变。新加入的点到其他各点的权值比原来的权值更小， 则替换！采取遍历的方法！j012345Lowcost04011002adjvex111416Lowcost = 0为我们已经选出来的顶点，接着继续在Lowcost中选出值不为

9、0的最小值，作为下一个最小生成树的点。这样一直选择下去直到选出所有的顶点。最小生成树建立，那么需要借用辅助数组，进行记录。int minimun(MGraph G,closedge F)(int i,min;for(i=0;i;i+)if(Fi.lowcost!=0) break;min=i;for(i=0;i;i+)if(Fi.lowcost!=0 &Fi.lowcostFmin.lowcost) min=i;return min;调试时，加入的函数，输出邻接矩阵和辅助数组，进行查看和判断正误。void PrintMatrix(MGraph &G)dj!=QM)coutij.adj”;els

10、e cout8 ;coutendl;void printclosedge(MGraph G,closedge X) owcost;coutendladjvex:；for(i=0;i;i+)cout Xi.adjvex;主程序。void main()(MGraph G;VertexType u;=0;CreateUDN(G);PrintMatrix(G);coutu;MiniSpanTree_PRIM(G,u);system(pause);普里姆(Prim)算法分析：Prim算法的时间复杂度主要是在双重循环构造最小生成树的过程中，设图 的顶点数为山则双重循环的时间复杂度为O(n2)，在生成最小生

11、成树的过程中， 增加了两个数组，closedge口和result 口数组，用来记录所选顶点的全趋结点， 故空间复杂度为O(2n)。普里姆算法的时间复杂度与边数e无关，该算法更适合 于求边数较多的带权无向连通图的最小生成树。普里姆(Prim)算法实验结果:采用的数据：6 112 3 4 5 62 41 4 33 25 34 43 54 16 25 66 26 41实验结果:D:Usersluo yiwenDesktoptesttest请输A蔓始的点d卵规成直为:i： 0 1 2 3 4 5loucost: 0423 100 100adjvex： 111111K的寻求结果为数组顿中的下标）:2 捕

12、寻求结果为数组顿中的下标）:3 3 4K的寻求结果为数组顿中的下标）：5K的寻求结果为（数组dg中的下标）:1H的寻求结果为（数组&我中的下标）:42 53 1 六.,时 权值3 1 六.,时 权值132411324162124请矗专键A-图表分析:(b)(a)(b)(a)(f)(f)结论与展望：运用prim算法构造图的最小生成树，使生成树的权值和达到最小，即耗费最小， 这里选择贪心策略，从一个顶点出发，选择到剩余顶点的边权值最小的顶点，将 之并入到所够造的生成树之中，同时修改剩下的顶点到生成 树的权值，再从剩 余顶点中继续选择到生成树耗费最小的顶点，继续并入该顶点，直到所有的顶点 全部并入到生成树中为止，其核心思想在于不断地在剩余顶点中选取到生成树 耗费最小的顶点，将之并入后，修改剩余顶点到生成树相应的权值