2022年Prim算法和Kruskal算法的Matlab实现.pdf

《2022年Prim算法和Kruskal算法的Matlab实现.pdf》由会员分享，可在线阅读，更多相关《2022年Prim算法和Kruskal算法的Matlab实现.pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Prim 算法和 Kruskal算法的 Matlab 实现计算机仿真期末大作业Prim 算法与 Kruskal 算法的 Matlab 实现05605刘禹 050697(30) 连线问题应用举例 : 欲铺设连接n个城市的高速公路, 若i城与j城之间的高速公路造价为ijC, 试设计一个线路图 , 使总的造价最低。连线问题的数学模型就就是图论中在连通的赋权图上求权最小的支撑树。试用Matlab 分别实现求最小支撑数的Prim 算法与 Krusal 算法 ( 避圈法 )。一、基本要求 : （1）画出程序流程图 ; （2）对关键算法、变量与步骤进行解释说明; （3）用如下两图对所写算法的正确性进行验证。

2、即输入图的信息, 输出对应图的最小支撑树及其权值。v1v7v6v4v5v3v2634212435216196611218302051514924167534844(4)分析两种算法的实现复杂度。二、扩展要求 : (1)提供对算法效率(复杂度 )进行评估的方法,并通过举例验证,与分析得到的算法复杂度结果相对照 ; (2)从降低内存消耗、减少计算时间的角度,对算法进行优化。三. 实验步骤I 、用 Prim 算法求最小生成树i.算法分析及需求分析,程序设计prim 算法的基本思想就是:设 G=(V,E)就是一个无向连通网,令 T=(U,TE) 就是 G 的最小生成树。 T 的初始状态为U=v0(v0

3、)TE=, 然后重复执行下述操作:在所有 uU, vV-U 的边中找一条代价最小的边(u,v)并入集合TE,同时 v 并入 U,直至 U=V 为止。显然 ,Prim 算法的基本思想就是以局部最优化谋求全局的最优化,而且 ,还涉及到起始结点的问题。本程序完成的功能就是:从图中的任意结点出发,都能够找出最小生成树实现方案分析 : Prim 算法的关键就是如何找到连接U 与 V-U 的最短边来扩充生成树T。设当前 T 中有k 个点 (即 T 的顶点集 U 中有 k 个顶点 )则所有满足uU,vV-U 的边最多有k条,从如此大的边集中选取最短边就是不太经济的。利用 MST 性质 ,可以用下述方法构造候

4、选最精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 14 页 - - - - - - - - - - Prim 算法和 Kruskal算法的 Matlab 实现小边集 :对应 V-U 中的每个顶点 ,保留从该顶点到U 中的各顶点的最短边,取候选边最短边集为 V-U 中的 n-k 个顶点所关联的n-k 条最短边的集合。为表示候选最短边集,需设置两个一维数组 lowcostn 与 adjvexn ,其中 lowcost 用来保存集合V-U 中的各顶点与集合U 中顶点的最短边的权值,lowcostv

5、=0 表示顶点 v已经加入最小生成树中;adjvex 用来保存依附于该边在集合 U 中的顶点。例如下式表明顶点与顶点之间的权值为w lowcosti=w; adjvexi=k; 程序流程图关键代码说明 : 1 将用于验证算法正确性的两幅图用邻接矩阵的形式保存,分别保存为文件Graph1、m,Graph2、m(注:矩阵的对角线元素设置为零。)并在主程序finallyprim 中直接进行调用。2 在输入起点时应该给程序的阅读者就该图的顶点数作出提示,不然的话使用者很可能会输入越界下标。采取的方法如下len=length(graph_adjacent);% 求图中有多少个顶点k=sprintf(pl

6、ease input the point where you want to start ,do remember it must be between 1 and %d ,len); start_point=input(k);% 输入最小生成树产生起点采取了 sprintf 格式化字符串的方法,就避免了编程的人每次根据输入图的顶点数手动对提示作修改。效果如下: 在对第一幅图进行算法验证时在workspace 会如下输出 : please input the point where you want to start ,do remember it must be between 1 精品资料

7、 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 14 页 - - - - - - - - - - Prim 算法和 Kruskal算法的 Matlab 实现and 7 在对第二幅图进行算法验证时在workspace 会有如下输出 : please input the point where you want to start ,do remember it must be between 1 and 8 3在输出结果时为了使结果在workspace 中输出的清晰,使人一目了然,也使用了sprintf

8、格式化字符串的方法,代码如下s=0; for ii=1:len-1 k=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); end disp(最小生成树的总代价为:) disp(s); 4下面对算法的核心部分进行说明: 在 len-1 次循环中 ,每次循环要完成以下三项工作1、找到最小边 ,(需要求 lowcost 数组的最小非零值,因为

9、 0 表示该边已经被加入到了最小生成树中) 由于就是求非零的最小值,就不能在直接用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(1);% 因为最小值的下标可能不止一个

10、,这里取第一个下标进行处理lowcost(index)=0;% 表明该节点已经加入了最小生成树中采用这种方法不仅充分利用了matlab 的 built_in 函数 ,还避免了自己编写代码 (循环 +判断 lowcostv 就是否为0)来实现寻找不为零的最小值的麻烦,提高了代码执行的效率。2、对 lowcost 与 adjvex 进行更新 ,即:设刚加入最小生成树的顶点为index, 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 14 页 - - - - - - - - - - Prim 算法

11、和 Kruskal算法的 Matlab 实现比较对于U-V 中的每个顶点v:比较 lowcost(v) 与(v,index)边的权值大小,如果(v,index) 边的权值小 ,则令 lowcost(v) 的值为该边的权值,并将 adjvex(v) 的值等于 index for j=1:len if lowcost(j)graph_adjacent(j,index); lowcost(j)=graph_adjacent(j,index); adjvex(j)=index; end end 3、将该边保存tree(i,:)=adjvex(index),index; ii、结果如下求第一张图的最小生

12、成树: 求第二张图的最小生成树: 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 14 页 - - - - - - - - - - Prim 算法和 Kruskal算法的 Matlab 实现II 、 用 Krusal 算法( 避圈法 )求最小生成树i.算法分析及需求分析,程序设计Kruskal 算法的基本思想就是:设无向连通网为G=(V,E), 令 G 的最小生成树为T=(U,TE),其初始状态为U=V ,TE=, 这样 T 中各顶点各自构成一个连通分量。然后按照边的权值由小到大的顺序 ,依次

13、考察边集E 中的各条边。若被考察的边的两个顶点属于T 的两个不同的连通分量 ,则将此边加入到TE 中去 ,同时把两个连通分量连接成一个连通分量;若被考察边的两个结点属于同一个连通分量,则舍去此边 ,以免造成回路,如此下去 ,当 T 中的连通分量个数为1时,此连通分量便为G 的一棵最小生成树。显然 ,Kruskal 算法实现起来要比prim 算法复杂些。选择合适的存储结构存储图,采用合适的排序算法对程序执行效率的提高非常重要,采用简单而明了的方法判断边的两个端点就是否在一个连通分支上更就是尤为重要。一般来说 ,涉及 Kruskal 算法多采取边集数组做为图的存储结构,但考虑到matlab 不像

14、C语言那样可以方便地动态的生成数组与释放内存,仍采取了邻接矩阵的形式保存图,用于测试的两幅图 ,分别保存为Graph11、M,Graph22 、M、(注:邻接矩阵的对角线元素设定为100)这样既方便对边进行操作,又方便对边的顶点进行操作。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 14 页 - - - - - - - - - - Prim 算法和 Kruskal算法的 Matlab 实现使用邻接矩阵容易引起的问题就是: 由于邻接矩阵就是对称矩阵,比如 graph_adjacent(1,2)

15、与 graph_adjacent(2,1)代表的就是同一条边 ,所以当有一条边被选入最小生成树后,要对它的两个结点分别进行更新。整个程序就是以顶点为基本单位处理的。由于一条边对应两个结点,取标号较小的顶点做为主要处理对象,并用它来寻址该边所对应的另一个结点。这样规格化的好处在于:程序流程的每一步都会在自己的预测中,出现了错误易于查找。下面介绍一下一个matlab 的 built_in 排序函数sort 这个函数的功能非常强,也正因为采用了这个函数才使我的程序简洁高效。Y,I=sort(A); 其中 A 为矩阵。则 Y 为将 A 中各列按从小到大排序后的结果,I为 Y 中的元素在原矩阵A 中所在

16、的行号。举例如下对于判断两个点就是否在同一个连通分支,我的方法如下 : 声明一数组tag 保存每个结点所在的连通分支的标号,初始值为每个结点的标号, 当两个连通分量相连后则将它们的tag 值设为一致程序流程图 : 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 14 页 - - - - - - - - - - Prim 算法和 Kruskal算法的 Matlab 实现关键代码说明 : 1 如何判断两个点就是否在同一个连通分支将图中每个顶点的tag 值设为自身标号for j=1:len tag(

17、j)=j;% 关联标志初始化,将每个顶点的关联标志设为其本身end; 当确定两个顶点不在同一个连通分支时,将它们对应的边加入最优边集superedge 中,并修改其中一个顶点的及其所在连通分支的各个点的tag 值,使其与另一连通分支具有相同的tag 值。if(tag(anotherpoint)=tag(index)% 当两个点不属于一个连通集时,这两个点之间的边为最小生成树的边superedge(i,:)=index,anotherpoint;% 将其加入最小生成树的边集中i=i+1;% 下标加 1 %下面的语句的作用就是将两个连通分支变成一个连通分支,即 tag 值一样for j=1:len

18、% 以 index 的 tag 值为标准if(tag(j)=tag(anotherpoint)&(j=anotherpoint)%遍搜 tag 数组 ,先将与 anotherpoint tag 值一样的点的tag 值变为 index 的 tag 值tag(j)=tag(index); end end tag(anotherpoint)=tag(index);% 将 anotherpoint 的 tag值变为 index 的 tag值精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 14 页 -

19、- - - - - - - - - Prim 算法和 Kruskal算法的 Matlab 实现end end 注意 :上面的红色代码部分,要先将连同分支的其她点的tag 值变为 tag(index), 最后在改变tag(anotherpoint) 的tag 值,如果先将tag(anotherpoint) 的值改变了,编号在anotherpoint 之后的点的tag 值就无法正确更新了2、寻找最小边Y,I=sort(temp);% 将 temp 的每列按从小到大排序,数组 Y 保存 temp 排序后的结果 ,I 中保存相应结果对应的在temp 中的下标cost_min=min(Y(1,:);%

20、找出权值最小的边index=find(Y(1,:)=cost_min);%找出权值最小的边对应的顶点index=index(1);% 一条边对应两个节点,且不同的边的权值可能一样,这里为了方便处理人为规定了顺序,取标号最小的顶点进行处理anotherpoint=I(1,index);% 找到该边对应的另一个顶点%将该边对应的权值修改为最大,防止该边在下次循环中再次被选为最优边temp(index,anotherpoint)=100; temp(anotherpoint,index)=100; 3、显示模块采用的代码参见prim 算法。ii、结果如下a 第一张图的最小生成树b 第二张图的最小生成

21、树精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 14 页 - - - - - - - - - - Prim 算法和 Kruskal算法的 Matlab 实现四.扩展功能的完成(1)提供对算法效率(复杂度 )进行评估的方法,并通过举例验证,与分析得到的算法复杂度结果相对照 ; 理论分析设图中的顶点数为n,则 Prim 算法要执行n-1 次外循环找齐最小边,每次外循环又要执行n次内循环对lowcost 与 adjvex 数组进行更新 ,所以 Prim 算法的时间复杂度为O(),与网中的边数无关

22、,因此适用于求稠密网的最小生成树。因为Kruskal算法就是依次对图中的边进行操作,因此Kruskal算法的时间复杂度为O(e),其中 e 为无向连通网中边的个数。相对 Prim 算法而言 ,Kruskal 算法适用于求稀疏网络的最小生成树。程序验证1 随机生成 300300 的对称稠密矩阵,用于观测Kruskal 与 Prim 算法的运行时间。 (分别在 finallyprim与 finallykruskal脚本文件中的主循环开始与结束为止加tic,toc) 对称矩阵采用如下方法生成。a=ceil*(rand(300); b=triu(a); c=b; a=a+c; for ii=1:300

23、 a(ii,ii)=0;%(for prim) or a(ii,ii)=1000%(for kruskal) end 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 14 页 - - - - - - - - - - Prim 算法和 Kruskal算法的 Matlab 实现运行结果如下 : a.prim b.kruskal 由此可见对于稠密图prim 算法优于 kruskal 算法2 随机生成一稀疏对称矩阵,用于观测 kruskal 与 prim 算法的运行时间稀疏对称矩阵采用如下方法生成a=

24、ones(300)*1000;% 如果 a(i,j)=1000 表明 i,j 两点不连通a(:,2)=ceil(50*rand(1,300); a(2,:)=a(:,2); a(1,3)=1; a(3,1)=1; a(4,8)=2; a(8,4)=1; for ii=1:300 a(ii,ii)=0;%(for prim) end 这就是一个多播网,2 号结点就是广播源,1,3 结点与 2 相连外 ,还彼此相连 ,同理 4,8 结点。运行结果如下 : a.Prim b.kruskal 3、结果对比 (时间单位seconds) 稀疏图稠密图精品资料 - - - 欢迎下载 - - - - - -

25、- - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 14 页 - - - - - - - - - - Prim 算法和 Kruskal算法的 Matlab 实现Prim 0、188 0、172 Kruskal 3、609 22、719 从表格的行的方向对比说明: prim 算法更适于处理稠密图;kruskal 算法更适于处理稀疏图。从表格的列的方向对比说明: 似乎就是prim 算法在两种场合都优于kruskal 算法 ,但这个结论就是不正确的,因为我的 kruskal 算法还没有达到最优化。(2)从降低内存消耗、减少计算时间的角度,对算法进行优化。1

26、、prim 算法对于 prim 算法,我认为在我的思路范围内已经达到了最优。尤其得意的就是寻找非零最小值的代码实现,认为很具有matlab 风格。k=lowcost0;%k 为一逻辑数组 ,它与 lowcost 同维 ,对于每一个位置i if lowcost(i)0 则 k(i)=1 %否则 k(i)=0; 稍候将用这个数组进行辅助寻址cost_min=min(lowcost(k);%找出 lowcost 中除 0 外的最小值index=find(lowcost=cost_min);%找出此最小值在lowcost 中的下标 ,即找到相应的节点index=index(1);% 因为最小值的下标可

27、能不止一个,这里取第一个下标进行处理lowcost(index)=0;% 表明该节点已经加入了最小生成树中2.Kruskal 算法对 Kruskal 算法,我有两点优化精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 14 页 - - - - - - - - - - Prim 算法和 Kruskal算法的 Matlab 实现修改后的代码如下: 修改后的代码更加充分的利用了matlab 语言的特性 ,与其 built_in 函数。用修改后的Kruskal 算法分别求图1,图 2 的最小生成树结果

28、如下图一 : 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 14 页 - - - - - - - - - - Prim 算法和 Kruskal算法的 Matlab 实现图二: 结果正确 ,说明改进后的Kruskal 算法正确用改进后的Kruskal 算法求上面两个测试算法时间复杂度的图的最小生成树结果如下a.稠密图b.稀疏图与 prim 算法时间对比如下稀疏图稠密图Prim 0、188 0、172 kruskal 0、203 0、063 这就很好的验证了结论:Prim 算法更适用于稠密图;

29、Kruskal 算法更适用于稀疏图。五、实验总结经过一个学期的对matlab 语言的学习与应用,已经能够熟练地使用matlab 来编程与仿真 ,对这次程序的代码感到特别满意。因为充分利用了matlab 语言的特性 ,使代码精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 14 页 - - - - - - - - - - Prim 算法和 Kruskal算法的 Matlab 实现非常紧凑与简练,如果这两个算法用C 语言实现的话,代码一定会比现在的复杂很多。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 14 页，共 14 页 - - - - - - - - - -