Prim算法和Kruskal算法的Matlab实现

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

2、树及其权值。(4)分析两种算法的实现复杂度。二 .扩展要求：(1)提供对算法效率(复杂度)进行评估的方法，并通过举例验证，与分析得到的算法复杂度结果相对照；(2)从降低内存消耗、减少计算时间的角度，对算法进行优化。三.实验步骤I.用Prim算法求最小生成树i.i.算法分析及需求分析，程序设计prim 算法的基本思想是：设 G=(V,E)是一个无向连通网，令 T=(U,TE)是 G 的最小生成树。T 的初始状态为 U=v0(v0E)TE=,然后重复执行下述操作：在所有 EU,vtV-U 的边中找一条代价最小的边(u,v)并入集合 TE,同时 v 并入 U,直至 U=V 为止。显然，Prim 算法

3、的基本思想是以局部最优化谋求全局的最优化，而且，还涉及到起始结点的问题。本程序完成的功能是：从图中的任意结点出发，都能够找出最小生成树实现方案分析：Prim 算法的关键是如何找到连接 U 和 V-U 的最短边来扩充生成树 T。设当前 T 中有 k个点（即 T 的顶点集 U 中有 k 个顶点）则所有满足 ufU,vfV-U 的边最多有璃似条，从如此大的边集中选取最短边是不太经济的。利用 MST 性质，可以用下述方法构造候选最小边集：对应 V-U 中的每个顶点，保留从该顶点到 U 中的各顶点的最短边，取候选边最短边集为 V-U 中的 n-k 个顶点所关联的 n-k 条最短边的集合。为表示候选最短边

4、集，需设置两个一维数组 lowcostnlowcostn和 adjvexnadjvexn,其中 lowcost 用来保存集合 V-U 中的各顶点与集合 U 中顶点的最短边的权值，lowcostv=0 表示顶点 v 已经加入最小生成树中；adjvex 用来保存依附于该边在集合 U 中的顶点。例如下式表明顶点和顶点熊之间的权值为 wlowcosti=w;adjvexi=k;程序流程图L输入开始焙点.如果输入的给点越界，即不在图中.则输出错误信息提示用户宣新输入。并对程序中要用到的数粗断初始化start_point=input(k);%输入最小生成树产生起点采取了 sprintf 格式化字符串的方法

5、，就避免了编程的人每次根据输入图的顶点数手动对提示作修改。效果如下：在对第一幅图进行算法验证时在 workspace 会如下输出：pleaseinputthepointwhereyouwanttostart,dorememberitmustbebetween1and7在对第二幅图进行算法验证时在 workspace 会有如下输出：pleaseinputthepointwhereyouwanttostart,dorememberitmustbebetween1and83.在输出结果时为了使结果在 workspace 中输出的清晰，使人一目了然，也使用了sprintf 格式化字符串的方法，代码如下

6、s=0;forii=1:len-1关键代码说明:1.将用于验证算法正确性的两幅图用邻接矩阵的形式保存,分别保存为文件Graph1.m,Graph2.m（注：矩阵的对角线元素设置为零。）并在主程序 finallyprim中直接进行调用。2.在输入起点时应该给程序的阅读者就该图的顶点数作出提示,能会输入越界下标。采取的方法如下len=length（graph_adjacent）;%求图中有多少个顶点不然的话使用者很可k=sprintf(pleaseinputthepointwhereyouwanttostart,dorememberitmustbebetween1and%d,len);士根据上一步

7、输入的开骐结点对lows日和mdNBi进行初赋值：工根据上一步输入的开始轴点对lci，85t和adjvexli断T初原隹kiwcost-gFaph_adjacenfftmrt_pcinL二上Klowc口5明的值为吊点占#artjpdiit的叔曲adjvex=start_poink*on则L庵n上谿d中所有元素的值都为初蛤节点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(i

8、i,1),tree(ii,2);enddisp(最小生成树的总代价为：,)disp(s);4.下面对算法的核心部分进行说明：在 len-1 次循环中，每次循环要完成以下三项工作1 .找到最小边，(需要求 lowcost 数组的最小非零值，因为 0 表示该边已经被加入到了最小生成树中)由于是求非零的最小值，就不能在直接用 min 函数了。我采取的方法是这样的：k=lowcost0;%k 为一逻辑数组，它和 lowcost 同维，对于每一个位%置 i 如果 lowcost(i)0 贝 Uk(i)=1%否则 k(i)=0;稍候将用这个数组进行辅助寻址cost_min=min(lowcost(k);%

9、找出 lowcost 中除 0 外的最小值index=find(lowcost=cost_min);%找出此最小值在 lowcost 中的下标，即找到相应的节点index=index(1);%因为最小值的下标可能不止一个，这里取第一个下标进行处理lowcost(index)=0;%表明该节点已经加入了最小生成树中采用这种方法不仅充分利用了 matlab 的 built_in 函数，还避免了自己编写代码(循环+判断 lowcostv是否为 0)来实现寻找不为零的最小值的麻烦，提高了代码执行的效率。2 .对 lowcost 和 adjvex 进行更新，即：设刚加入最小生成树的顶点为 index,比

10、较对于 U-V 中的每个顶点 v:比较 lowcost(v)和(v,index)边的权值大小，如果(v,index)边的权值小，则令 lowcost(v)的值为该边的权值，并将 adjvex(v)的值等于 indexforj=1:leniflowcost(j)graph_adjacent(j,index);lowcost(j)=graph_adjacent(j,index);adjvex(j)=index;endend3 .将该边保存tree(i,:)=adjvex(index),index;ii.ii.结果如下求第一张图的最小生成树：pltaseinputthepointwhereyouwa

11、nttostart3Mr&ui&jnberitmustbebetwten1and72最小生成树的总代价为:15最小生成树第I条边:权值为3最小生成树第2条边最小生成树匏3条边:最小生成树第4条边E最小生成树匏5条边:最小生成树第6条边(1,(3)(1,(3)值为2( (3,6),权值为16,7),权值为2(6,5，权值为3(1,(4)(1,(4)值为4pleaseinputthepointwhereyouward:tostartdorejiLemberitmustbebetween1arLti75最小生成树的总代价为:15求第二张图的最小生成树:pleaseinputthepointwhere

12、youvanttostart7dorememberitmustbebetween1arid84最小生成树第1条边E最小生成树第3 条边:最小生成树的总代价为:60pleaseinputthepointwhereyouwanttostartdorememberitmustbebetween1and88最小生成树的总代价为:60Kruskal 算法的基本思想是：设无向连通网为 G=(V,E),令 G 的最小生成树为 T=(U,最小生成树第 1 条边: (5,6),权值为 3最小生成树第 2 条边: (6,3),权值为 1最小生成树第 3 条边:(3,1)-权值为 2最小生成树第 4 条边: (6,

13、7),权值为 2最小生成树第 5 条边: (1,2)，权值为 3最小生成树第 6 条边: (1,4)，权值为 4最小生成树第 2 条边:(3,5)，权值为2最小生成树第4 条边: (3,6)(3,6), ,权值为国最小生成树第5 条边: (6,7)(6,7), ,板值为5最小生成树第吕条边:&).最小生成树第条边: (1,2)(1,2), ,权值为 9最小生成树第1条边:8,4)，权值为日最小生成树第2帮边,极值为6最小生成树第3条边tC3.5),权值知2最小生成树第4条边:权11为重最小生成树第5条边,(6,7) 权值为5最小生成树第E条边t (63)r根值为14最小生成树第条边:(1,2)

14、.权值为9II.用Krusal算法(避圈法)求最小生成树i.i.算法分析及需求分析, 程序设计TE),其初始状态为 U=V,TE=,这样 T 中各顶点各自构成一个连通分量。然后按照边的权值由小到大的顺序，依次考察边集 E 中的各条边。若被考察的边的两个顶点属于 T 的两个不同的连通分量，则将此边加入到 TE 中去，同时把两个连通分量连接成一个连通分量；若被考察边的两个结点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当 T中的连通分量个数为 1 时，此连通分量便为 G 的一棵最小生成树。显然，Kruskal 算法实现起来要比 prim 算法复杂些。选择合适的存储结构存储图，采用合适的

15、排序算法对程序执行效率的提高非常重要，采用简单而明了的方法判断边的两个端点是否在一个连通分支上更是尤为重要。一般来说，涉及 Kruskal 算法多采取边集数组做为图的存储结构，但考虑到 matlab 不像C 语言那样可以方便地动态的生成数组和释放内存，仍采取了邻接矩阵的形式保存图，用于测试的两幅图，分别保存为 Graph11.M,Graph22.M.(注：邻接矩阵的对角线元素设定为 100)这样既方便对边进行操作，又方便对边的顶点进行操作。使用邻接矩阵容易引起的问题是：由于邻接矩阵是对称矩阵，比如 graph_adjacent(1,2)和 graph_adjacent(2,1)代表的是同一条边

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

17、点是否在同一个连通分支，我的方法如下：声明一数组 tag 保存每个结点所在的连通分支的标号，初始值为每个结点的标号,当两个连通分量相连后则将它们的 tag 值设为一致程序流程图:L相关变量初始化工作， 将原图的邻接矩阵拷贝到馆mp矩阵中，避免程序对原矩阵直接进行修改2.找最小生成树（采用while循环，因为循环次数事先并不知道）循环结束条件为找到了顶点数-1条最优边3.求最小生成树的总代价并显示，并显示最小生成树的边，及其权值关键代码说明：1 .如何判断两个点是否在同一个连通分支将图中每个顶点的 tag 值设为自身标号forj=1:lentag(j)=j;%关联标志初始化，将每个顶点的关联标志

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

19、tag(anotherpoint)&(j-=anotherpoint)%遍搜 tag 数组，先将和 anotherpointtag 值一样的点的 tag 值变为 index 的 tag 值tag(j)=tag(index);endendtag(anotherpoint)=tag(index);%将 anotherpoint 的 tag 值变为 index 的 tag 值endend注意：上面的红色代码部分，要先将连同分支的其他点的 tag 值变为 tag(index),最后在改变 tag(anotherpoint)的 tag 值，如果先将 tag(anotherpoint)的值改变了，编号在a

20、notherpoint 之后的点的 tag 值就无法正确更新了2 .寻找最小边Y,I=sort(temp);%将 temp 的每列按从小到大排序，数组 Y 保存 temp 排序后的结果，I 中保存相应结果对应的在 temp 中的下标cost_min=min(Y(1,:);%找出权值最小的边index=find(Y(1,:)=cost_min);%找出权值最小的边对应的顶点index=index（1）;%一条边对应两个节点，且不同的边的权值可能一样，这里为了方便处理人为规定了顺序，取标号最小的顶点进行处理anotherpoint=I（1,index）;%找到该边对应的另一个顶点%将该边对应的权值

21、修改为最大，防止该边在下次循环中再次被选为最优边temp（index,anotherpoint）=100;temp(anotherpoint,index)=100;3 .显示模块采用的代码参见 prim 算法。ii.ii.结果如下a.第一张图的最小生成树最小生成树的总代价为:15b.第二张图的最小生成树最小生成树第 1 1 条边，最小生成树第 2 2条边二最小生成树第3 3 条边，最小生成树第 4 4 条边工最小生成树笫 5 5 条边.最小生成树第 6 6 条边工最小生成树第条边，（3,53,5）, ,权值为 2 2（66），权值为 5 5C3j4C3j4）, ,极值为 6 6（% %8 8）

22、, ,权值为 6 6Clj2Clj2），极值为 9 9（1,61,6）, ,权值为 1414最小生成树第 1 1 条边最小生成树第 2 2 条边;最小生成树第 3 3 条边;最小生成树第 4 4 条边:最小生成树第 5 5 条边;:（工 6 6）, ,权值为 1 1（1,31,3），权值为 2 2（6.76.7），权值为 2 21 1L2L2）权值为 3 3（5 5 评），权值为 3 311141114），权值为 4 46 6）, ,权值为 1818最小生成树的总代价为工6060四.扩展功能的完成(1)(1)提供对算法效率(复杂度)进行评估的方法，并通过举例验证，与分析得到的算法复杂度结果相对

23、照；理论分析设图中的顶点数为 n,则 Prim 算法要执行 n-1 次外循环找齐最小边，每次外循环又要执行n 次内循环对 lowcost 和 adjvex 数组进行更新，所以 Prim 算法的时间复杂度为 0(，与网中的边数无关，因此适用于求稠密网的最小生成树。因为 Kruskal 算法是依次对图中的边进行操作，因此 Kruskal 算法的时间复杂度为 O(e),其中 e 为无向连通网中边的个数。相对 Prim 算法而言，Kruskal 算法适用于求稀疏网络的最小生成树。程序验证1 .随机生成 300300 的对称稠密矩阵，用于观测 Kruskal 和 Prim 算法的运行时间。(分别在 fi

24、nallyprim 和 finallykruskal 脚本文件中的主循环开始和结束为止加 tic,toc)对称矩阵采用如下方法生成。a=ceil*(rand(300);b=triu(a);c=b;a=a+c;forii=1:300a(ii,ii)=0;%(forprim)ora(ii,ii)=1000%(forkruskal)end运行结果如下：a.primpleaseinputthepointriiereyouwanttostart,dorememberitmustbebetween1and3005Elapsedtineis0*172000seconcls;最小生成树的总代价为：b.krus

25、kalElapsedtinsic22.719000营自小8面,最小生成朝晌总代除为：300由此可见对于稠密图 prim 算法优于 kruskal 算法2 .随机生成一稀疏对称矩阵，用于观测 kruskal 和 prim 算法的运行时间稀疏对称矩阵采用如下方法生成a=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;forii=1:300a(ii,ii)=0;%(forprim)end这是一个多播网，2 号结

26、点是广播源，1,3 结点和 2 相连外，还彼此相连，同理 4,8 结点。运行结果如下：a.Primpleaseinputth.pointwhereyouwanttostartjdoreniemberitmu5thebetween1and3005Elapsedtimeis01880D0secondc.量小生成树的总代价为7337b.kruskalFlapsedFlapsedtimeistimeis3.3.609000609000seconds.seconds.最小生成树的总代价为工73373.结果对比(时间单位 seconds)稀疏图稠密图Prim0.1880.172Kruskal3.60922

27、.719从表格的行的方向对比说明：prim 算法更适于处理稠密图；kruskal 算法更适于处理稀疏图。从表格的列的方向对比说明：似乎是 prim 算法在两种场合都优于 kruskal 算法，但这个结论是不正确的，因为我的 kruskal 算法还没有达到最优化。(2)(2)从降低内存消耗、减少计算时间的角度，对算法进行优化。对于 prim 算法，我认为在我的思路范围内已经达到了最优。非零最小值的代码实现，认为很具有 matlab 风格。k=lowcost0;%k 为一逻辑数组，它和 lowcost 同维，对于每一个位置 iiflowcost(i)0 贝 Uk(i)=1%否则 k(i)=0;稍候

28、将用这个数组进行辅助寻址cost_min=min(lowcost(k);%找出 lowcost 中除 0 外的最小值index=find(lowcost=cost_min);%找出此最小值在 lowcost 中的下标，即找到相应的节点index=index(1);%因为最小值的下标可能不止一个，这里取第一个下标进行处理lowcost(index)=0;%表明该节点已经加入了最小生成树中2.Kruskal 算法对 Kruskal 算法，我有两点优化口个欣K品匚,，山以苞士法有方更,歙1我才漾#篁个邻蟆南8行重拉-阻虹一诲产喈海邙断口两支心生粗邛娥随进曲序更翻项灯jhile(suptreie(Im

29、-1dl)=Q一在巫叵%嗝丽列前Wl用大杵陶嫡T限存trp搏序后的结新I中脑用嶙刎度的在teip中的下标如stjiimuiOfUr；蛾出我曾星小的立11曲中五4(1(1屈NCOBtjda);他由极值呈+的边对区的顶点代比=in如出;上岫对丽卞节焉且不同的边的权值哨ET，这里为了方便妇以为魁了胡 联标号小的顶点进行处理aurtherpoiTit=Kljinds:):戒电阖也对应的另一千顶点蝶鼬梅的施懿为最尢处睡在下燔脚再施燃就过tEKP(uirlfii,anotherpfliirt)=M,f 叩(anrrthetpoint,inidezl=OD,if(tagtflurtbarpoiirt)W就t

30、indn)：省麻好用工一力连 W.引t二q十卢之间的达为最小上酬於sQpeiedgitijiJ-tir.deK,aMthecpoiHtJ小iQA靶-生恻射电集中i=i+l;*F就门轩施语句的概耨两馈置域在 T 政分堂附或上for-1:LD喟:indai的值为标准if.(arintherpuintmuthsijoint)t扰加( (DldM) )；etudmdtag(iJbdH):啮的t型触场end修改后的代码如下:尤其得意的是寻找1314151617181520212223我25加27将293D3L323X比36月概a洪融先尊君aicrtherpointtaj喟一样欣点的t线做.为七击工班就值

31、有UT.U冽而t弱小5底节在整个很 中飘一凯聪蒯 西宣京的软鞋初硅卜珊h哪1先建下当蠲-港幽力用 T 例班般(即藤吉值忆期中出现普TS!较，这用囹嘘博麦的13首融成出连通度L遮相额可口了的t量小生成树的总代馆为:60结果正确，说明改进后的 Kruskal 算法正确：昆1二期出加期；心1屋曜犯叫e%tH；L)=S丽岫汕i陋1,；陶蹴Si小褴irjdss=fiftd(T(lhJ=cB?+.iiTJ;】1-181520202-222324-252626- -打.28-1依E：31-3233-扯出iruift华 H 司山如1)：你皂ta洲目平日,匕旧翻月的土if世崛MsuhlDlenjtMsMM燃即唯时支财欺 择催思t驾似处2乂时(anrithjfixjiflijit).tnnd1知扯言),riset驾|：扯l)=taj(mdes),Junes41则他(疝bl);37-etd际%计即！=su:rtftg叩口j武鼎孙耽惟印血7)?宜:U血&SMtlueiptiintJ=ytip;M：Jiijd%油Mbs型M