《Prim算法和Kruskal算法的Matlab实现》由会员分享，可在线阅读，更多相关《Prim算法和Kruskal算法的Matlab实现（16页珍藏版）》请在金锄头文库上搜索。
1、计算机仿真期末大作业Prim 算法和 Kruskal 算法的 Matlab 实现05605 刘禹 050697（30）连线问题应用举例：ij欲铺设连接n个城市的高速公路，若i城与j城之间的高速公路造价为C.,试设计 一个线路图，使总的造价最低。 连线问题的数学模型就是图论中在连通的赋权图上求权最小的支撑树。试用 Matlab 分别实现求最小支撑数的 Prim 算法和 Krusal 算法（避圈法）。一.基本要求：（1）画出程序流程图；（2）对关键算法、变量和步骤进行解释说明；（3）用如下两图对所写算法的正确性进行验证。即输入图的信息，输出对应图 的最小支撑树及其权值。（4）分析两种算法的实现复杂
2、度。二.扩展要求：（1）提供对算法效率（复杂度）进行评估的方法，并通过举例验证，与分析得到的算 法复杂度结果相对照；（2）从降低内存消耗、减少计算时间的角度，对算法进行优化。三实验步骤I. 用Prim算法求最小生成树i. 算法分析及需求分析，程序设计prim算法的基本思想是：设G= （V, E）是一个无向连通网，令T= （U, TE）是G的最小生成树。T的初始状态为U=vO（vO三）TE=,然后重复执行下述操作：在所有u三U,vV-U的边中找一条代价最小的边（u, v）并入集合TE,同时v并入U,直至U=V为止。显然, Prim 算法的基本思想是以局部最优化谋求全局的最优化,而且,还涉及到起始
3、 结点的问题。本程序完成的功能是：从图中的任意结点出发,都能够找出最小生成树实现方案分析：Prim算法的关键是如何找到连接U和V-U的最短边来扩充生成树T。设当前T中有k 个点(即T的顶点集U中有k个顶点)则所有满足uU, vV-U的边最多有k- 条，从如此大的边集中选取最短边是不太经济的。利用MST性质，可以用下述方法构造候选最 小边集：对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边，取候选边最短 边集为V-U中的n-k个顶点所关联的n-k条最短边的集合。为表示候选最短边集，需设置两 个一维数组lowcostn和adjvexn,其中lowcost用来保存集合V-U中的各顶点与集合
4、U中 顶点的最短边的权值，1 owcostv=0表示顶点v已经加入最小生成树中；adjvex用来保存依 附于该边在集合U中的顶点。例如下式表明顶点和顶点二之间的权值为wlowcosti=w; adjvexi=k;程序流程图1输凡开始结点，如果输凡的结点越界，即不在图中，则输出错误信息提示用户重新输 兀 并对程序中要用到的数组进行初始化a djvex二st artjp oint * on es (lje n );%adjvex中所有元i素的值都为初贻节点召根据上一步输只一的开始塔点Mlowcostadjvex进行初赋值：2根据上一步输/的开岁 结点对 low co mt 和臼 djvex 进行初
5、赋值：lowco st =grap hadj acentfst artjp oint,:);% lowco H (i)的 值如韦点i与st artp oiri啲初i;3.Wlen-lbn为图中的顶点数)次循环，每初选出一条最优边填入最小生成树中数组tr弐中)O并对OTJ CO或和阴朋谜行更新，确保0CO5t用来保存集合*4J中的各顶点与集合U中顶点的最短边的权值，阴曲即来保存依附于该边在集合U中的顶点关键代码说明：1 将用于验证算法正确性的两幅图用邻接矩阵的形式保存， 分别保存为文件Graphl.m,Graph2.m (注：矩阵的对角线元素设置为零。)并在主程序finallyprim 中直接进
6、行调用。2 在输入起点时应该给程序的阅读者就该图的顶点数作出提示，不然的话使用者很可 能会输入越界下标。采取的方法如下len=length(graph_adjacent);% 求图中有多少个顶点 k=sprintf(please input the point where you want to start ,do remember it must be between 1 and %d ,len);start_point=input(k);%输入最小生成树产生起点采取了 sprintf 格式化字符串的方法，就避免了编程的人每次根据输入图的顶点 数手动对提示作修改。效果如下：在对第一幅图进行算
7、法验证时在 workspace 会如下输出:please input the point where you want to start ,do remember it must be between 1 and 7在对第二幅图进行算法验证时在 workspace 会有如下输出： please input the point where you want to start ,do remember it must be between 1 and 83 在输出结果时为了使结果在 workspace 中输出的清晰，使人一目了然，也使用了 sprintf 格式化字符串的方法，代码如下s=0;for
8、 ii=l:len-lk=sprintf(最小生 成树第%d 条边：(%d,%d ),权值 %d,ii,tree(ii,1),tree(ii,2),graph_adjacent(tree(ii,1),tree(ii,2);disp(k);disp(); s=s+graph_adjacent(tree(ii,1),tree(ii,2);enddisp(最小生成树的总代价为：)disp(s);4 下面对算法的核心部分进行说明：在 len-1 次循环中，每次循环要完成以下三项工作1.找到最小边，(需要求lowcost数组的最小非零值，因为0表示该边已经被加 入到了最小生成树中)由于是求非零的最小值，
9、就不能在直接用min函数了。我采取的方法是这 样的：k=lowcost0;%k为一逻辑数组，它和lowcost同维，对于每一个位% 置 i 如果 lowcost(i)0 则 k(i)=1 %否则k(i)=0;稍候将用这个数组进行辅助寻址cost_min=min(lowcost(k);%找出 lowcost 中除 0 外的最小值 index=find(lowcost=cost_min);%找出此最小值在 lowcost 中的下标， 即找到相应的节点index=index;因为最小值的下标可能不止一个，这里取第一个下标进行处理Iowcost(index)=0;%表明该节点已经加入了最小生成树中采用
10、这种方法不仅充分利用了 matlab 的 built_in 函数，还避免了自己 编写代码(循环+判断lowcostv是否为0)来实现寻找不为零的最小值的 麻烦，提高了代码执行的效率。2. 对 lowcost 和 adjvex 进行更新，即：设刚加入最小生成树的顶点为 index，比较对于U-V中的每个顶点v:比较lowcost(v)和(v, index)边的权值大 小，如果(v，index)边的权值小，则令lowcost(v)的值为该边的权值，并 将adjvex(v)的值等于indexfor j=l:lenif lowcost(j)graph_adjacent(j,index); lowcos
11、t(j)=graph_adjacent(j,index); adjvex(j)=index;endend3. 将该边保存tree(i,:)=adjvex(index),index;ii结果如下求第一张图的最小生成树：please input the point where you wmt to st art do reiTLeiTLber it must be between 1 宜nd 7 2最小生成树第1条边：(2, D ,最小生成树第2务边：(1, 3),权值駆最小生成树第3务边：(3, 6),权值曲1最小生成树第!务边：(6, 7),权值曲2最小生成树第5条边：(6, 5),权值炕最小
12、生成树第&务边：(1,4),权值曲q最小生成树的总代价曲:15please input the point where you want to st art j do remember it must be between 1 and 7 5最小生成树第1条边:(5, 6),最小生成树第2条边：(6, 3),权值曲1最小生成树第3务边：(3, 1),权值为2最小生成树第俸边:(6, 7),权值負2最小生成树第5条边：1,2),权值却最小生成树第E务边：(1,4),权值拘4最小生成树的总代价为:15求第二张图的最小生成树：pl已ase input the point where you want
13、 to start j do remember it must be between 1 and 8 4最小生战树第1条边：(4, 3),权值拘&最小生战树第2条边：(3, 5),权值拎2最小生成树第3条边：(4, 8),权值拘E最小生成树第4条边：(3, 6),权值拘18最小生成树第5条边：(6, 7),权值为5最小生战树第&祭边：C6, 1),权值掬14最小生成树第T条边：(13 2),权値删最小生成树的总代价曲：60please input the point where you want to start j do remember it must be between 1 and 8
14、 8最小生成树第1条边：(8,4),，权値触最小生成树第2祭边：(4, 3),，权值如最小生成树第3条边：(3, 5),，权值曲2最小生成树第4条边：(3, 6),，权値対18最小生成树第5祭边：(6, 7),，权值为5最小生成树第6条边：(6, 1)，权値曲14最小生成树第F祭边：(1, 2),，权值知最小生成树的总代价為：60II用Krusal算法（避圈法）求最小生成树i.算法分析及需求分析，程序设计Kruskal算法的基本思想是：设无向连通网为G=（V，E）,令G的最小生成树为T= （U,TE）,其初始状态为U=V, TE=,这样T中各顶点各自构成一个连通分量。然后按照边的 权值由小到大
15、的顺序，依次考察边集E中的各条边。若被考察的边的两个顶点属于T的两 个不同的连通分量，则将此边加入到TE中去，同时把两个连通分量连接成一个连通分量； 若被考察边的两个结点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T 中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。显然， Kruskal 算法实现起来要比 prim 算法复杂些。选择合适的存储结构存储图，采用 合适的排序算法对程序执行效率的提高非常重要，采用简单而明了的方法判断边的两个端点 是否在一个连通分支上更是尤为重要。一般来说，涉及Kruskal算法多采取边集数组做为图的存储结构，但考虑到matlab不像 C 语言那样可以方便地动态的生成数组和释放内存，仍采取了邻接矩阵的形式保存图，用于 测试的两幅图，分别保存为Graph11.M,Graph22.M.(注：邻
