Prim算法和Kruskal算法地Matlab实现

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

2、1）提供对算法效率（复杂度）进行评估的方法，并通过举例验证，与分析得到的算 法复杂度结果相对照；（2）从降低内存消耗、减少计算时间的角度，对算法进行优化。三实验步骤I.用Prim算法求最小生成树i 算法分析及需求分析，程序设计prim算法的基本思想是：设 G= （V, E）是一个无向连通网，令T= （ U, T日是G的最小生成树。T的初始状态为U=v0 （v0W）TE=，然后重复执行下述操作：在所有UU,vWV-U的边中找一条代价最小的边（u, v）并入集合TE同时v并入U,直至U=V为止。显然，Prim算法的基本思想是以局部最优化谋求全局的最优化，而且，还涉及到起始结点的问题。本程序完成的功

3、能是：从图中的任意结点出发，都能够找出最小生成树实现方案分析：Prim算法的关键是如何找到连接U和V-U的最短边来扩充生成树T。设当前T中有k个点(即T的顶点集U中有k个顶点)则所有满足 uwU, GV-U的边最多有k - 条，从如此大的边集中选取最短边是不太经济的。利用MST性质，可以用下述方法构造候选最小边集：对应V-U中的每个顶点，保留从该顶点到 U中的各顶点的最短边，取候选边最短边集为V-U中的n-k个顶点所关联的n-k条最短边的集合。为表示候选最短边集，需设置两个一维数组lowcostn和adjvexn,其中lowcost用来保存集合 V-U中的各顶点与集合 U中顶 点的最短边的权值

4、，lowcostv=0 表示顶点v已经加入最小生成树中；adjvex用来保存依附于该边在集合 U中的顶点。例如下式表明顶点和顶点，之间的权值为 wlowcosti=w;adjvexi=k;程序流程图ulfc入开靈乩 如般入的姑点枝乐 前锂刊 则輸lL惜误信息柠示再户重护肓 A.井珥唸序中君庄孰嫌魁进亍溯41adJveKflHrtjlDinT .* an bi (ile-n 上仙 d|we« 中浙 Wtl J 旳直都为初箱呼旦r崔器上一出角几萨节与色点对loEHt轴的左杆划限隹：r和据上一打输入鬥开堆 牯点对試價：IvwudsI gj up h_ a dj d CEni(s tarl_

5、p amtd:wco bt (i赫计算最小主虎制的件代你 井屈冠 叼卩显市孙晶*味耐旳匹点"讣叩杭1T关键代码说明:1. 将用于验证算法正确性的两幅图用邻接矩阵的形式保存，分别保存为文件Graph1.m,Graph2.m (注：矩阵的对角线元素设置为零。)并在主程序 fin allyprim中直接进行调用。2. 在输入起点时应该给程序的阅读者就该图的顶点数作出提示，不然的话使用者很可能会输入越界下标。采取的方法如下len=le ngth(graph_adjace nt);%求图中有多少个顶点k=spri ntf('pleasein put the point where yo

6、u want to start ,do rememberit must be betwee n 1 and %d ',le n);start_poi nt=i nput(k);%输入最小生成树产生起点采取了 sprintf 格式化字符串的方法，就避免了编程的人每次根据输入图的顶占八、数手动对提示作修改。效果如下：在对第一幅图进行算法验证时在workspace会如下输出：please in put the point where you want to start ,do remember it must bebetwee n 1 and 7在对第二幅图进行算法验证时在workspace

7、会有如下输出：please in put the point where you want to start ,do remember it must bebetwee n 1 and 83. 在输出结果时为了使结果在workspace中输出的清晰，使人一目了然，也使用了spri ntf格式化字符串的方法，代码如下s=0;for ii=1:le n-1k=sprintf('最小生成树第 %d条边：(%d,%d), 权值为 d',ii,tree(ii,1),tree(ii,2),graph_adjacent(tree(ii,1),tree(ii,2)；disp(k);disp(&

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

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

10、ost和adjvex进行更新，即：设刚加入最小生成树的顶点为index，比较对于 U-V中的每个顶点 v:比较lowcost(v)和(v，index)边的权值大 小，如果(v，index )边的权值小，则令lowcost(v)的值为该边的权值，并将adjvex(v)的值等于indexfor j=1:le nif lowcost(j)>graph_adjace nt(j,i ndex); lowcost(j)=graph_adjace nt(j,i ndex); adjvex(j)=in dex;endend3. 将该边保存tree(i,:)=adjvex(i ndex),i ndex;i

11、i.结果如下求第一张图的最小生成树：pleaise input the point where you want toj do rentniber itbe between 1 and 7 2累小生战材第1祭边：（2,1），权值为3最小空成树第屎边， 最小生威树第瑶边:最小坐威材第4祭边: 最小生成树第皤边;最小生威树第6条边匕(1.3) *权值为2(X 6)»权值为1(6,7)权H为2(6,5)，权値为3(1.4) *权值为4最小生咸树的总代价为;15pllease input "ike point nEere ynu wan+ +o start da> remem

12、ber i± must be between 1 anti 7最小主威材第1朵边:CEf6) i权值曲3蛊牛生戍樹第2築边:【£3J ,靱值划乞门圾值加最小主戍啊算q诱ii；（6,7）-杈值为E最小圭成柑第5蚤追:（1,2）,叔值为$量卜主咸删覘Mu（b4）,杈值曲q最小圭威樹的扁代价为：15求第二张图的最小生成树：please input tke pflint wfiere you want + q si:art / do r&uiew.'ber if jt.i_is+ be betwaan 1 and S 4垠4生威树笫1金边：枚値为眾小燮咸牺第2爭边.

13、【3,引極值曲2摄小兰威榊第3案边：心），权值負丘蚩冲生成枫黑4承边| （禺C栋值为代量小莹威桶第E編迪，f 枚值为B重才生咸树第6条边；C6, D杈11为14摄沙尘砂州第f集边：C1.2),职值用9最4注成树的总代析舟6Dplease LiWirt rhe pcint nrhere you varrt to rtsrt j do renenber it T.uft be between L and 8 B 搂水生成树弟1条边M幅,心袄值为丘毎小生悶阿芾？务谕：（4,3）朽佰帥H星小土删菜J条边乂:亠5） 栈值为2摄小生朋箱4条边.(3$) *模值为19卡小生威材梓匕制加【需门*朽僭亦臥T住删

14、粗条也:£：），枚值対M最小生删帶滦也门，门 > 袄值掬9悵4v：T战恭1时嘉仕愉为:60II . 用Krusal算法（避圈法）求最小生成树i 算法分析及需求分析，程序设计Kruskal算法的基本思想是：设无向连通网为G=（V, E）,令G的最小生成树为 T= （ U,TE）,其初始状态为 U=V, TE=,这样T中各顶点各自构成一个连通分量。然后按照边的权值由小到大的顺序，依次考察边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边加入到TE中去，同时把两个连通分量连接成一个连通分量；若被考察边的两个结点属于同一个连通分量，则舍去此边，以免造成回路，如

15、此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。显然，Kruskal算法实现起来要比 prim算法复杂些。选择合适的存储结构存储图，采 用合适的排序算法对程序执行效率的提高非常重要，采用简单而明了的方法判断边的两个端点是否在一个连通分支上更是尤为重要。一般来说，涉及 Kruskal算法多采取边集数组做为图的存储结构，但考虑到matlab不像C语言那样可以方便地动态的生成数组和释放内存，仍采取了邻接矩阵的形式保存图，用于测试的两幅图，分别保存为Graph11.M,Graph22.M.(注：邻接矩阵的对角线元素设定为100)这样既方便对边进行操作，又方便对边的顶点进行操作。使

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

17、。则Y为将A中各列按从小到大排序后的结果，I为Y中的元素在原矩阵 A中所在的行号。 举例如下当两个连通分量相连后则将它们的tag值设为一致程序流程图:关键代码说明：1 如何判断两个点是否在同一个连通分支 将图中每个顶点的tag值设为自身标号for j=1:le n tag(j)=j;%关联标志初始化，将每个顶点的关联标志设为其本身en d; 当确定两个顶点不在同一个连通分支时，将它们对应的边加入最优边集superedge中，并修改其中一个顶点的及其所在连通分支的各个点的tag值，使其和另一连通分支具有相同的tag值。if(tag(a notherpoi nt)=tag(i ndex)%当两个点

18、不属于一个连通集时，这两个点之间的边为最小生成树的边superedge(i,:)=i ndex,a no therpoi nt;%将其加入最小生成树的边集中i=i+1;% 下标加1%下面的语句的作用是将两个连通分支变成一个连通分支，即tag值一样for j=1:len%以 index 的 tag 值为标准if(tag(j)=tag(anotherpoint)&(j=anotherpoint)%遍搜tag数组，先将和 anotherpoint tag值一样的点的tag值变为index的tag值tag(j)=tag(i ndex);endendtag(anotherpoint)=tag(i

19、ndex);%将 anotherpoint的 tag 值变为index 的 tag 值endend注意：上面的红色代码部分，要先将连冋分支的其他点的tag值变为tag ( index)，最后在改变 tag ( anotherpoint )的tag 值，如果先将 tag(anotherpoint) 的值改变了，编号在anotherpoint 之后的点的tag值就无法正确更新了2. 寻找最小边Y,I=sort(temp);%将temp的每列按从小到大排序，数组Y保存temp排序后的结果，I中保存相应结果对应的在temp中的下标cost_mi n=mi n( Y(1,:);%找出权值最小的边in d

20、ex=fi nd(Y(1,:)=cost_mi n);%找出权值最小的边对应的顶点in dex=in dex(1);%一条边对应两个节点，且不同的边的权值可能一样，这里为了方便处理人为规定了顺序，取标号最小的顶点进行处理ano therpoi nt=l(1,i ndex);%找到该边对应的另一个顶点%将该边对应的权值修改为最大，防止该边在下次循环中再次被选为最优边|temp(i ndex,a no therpo in t)=100;temp(a no therpo in t,i ndex)=100;3. 显示模块采用的代码参见prim算法。ii.结果如下a.第一张图的最小生成树棗小生成拥第1峯

21、边：3而，权丽1绘小生战拥第2簾边：1,3,杈 18 为 2最小生战树第3条边1爲门-权值为2最小生成树第4簾边|1, A .取值为3最小生成树第5条边：瓦罰，叔值为3最小生成树第6条边：1沁)，权值和Q最屮生咸树的总代价比;15b.第二张图的最小生成树绘小生咸牺第1条边1(3,5) 1权值为2最小生成树第2象边：(6,7) 权值桃彘小生成树第3条边：彘小生成树弟4兼边；m权 136最小生成树弟弓兼边；(U2)-权備切最小生成树弟弓兼边：(1,6)，最小生咸树第r祭边：(3,6) *权値为18最小生成树的总代价対：60四.扩展功能的完成(1 )提供对算法效率(复杂度)进行评估的方法，并通过举例

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

23、prim 和finallykruskal脚本文件中的主循环开始和结束为止加tic,toc )对称矩阵采用如下方法生成。a=ceil*(ra nd(300);b=triu(a);c=b'a=a+c;for ii=1:300a(ii,ii)=0;%(for prim)or a(ii,ii)=1000%(for kruskal)end运行结果如下：a. primpie aff 9 injjut the pnixvt vhere you vartt 1 et azt , do r Braenbr jt mjjFt bs betvssri 1 and 00 E Elapsed Tims Is 0

24、» 172000 second;.景小生戍M的翟代价蓟i300b. kruskalEiarFR t：hf ip ?7fngnin 即耐“焦*涼小生删対总忙怖为，300由此可见对于稠密图prim算法优于kruskal算法2. 随机生成一稀疏对称矩阵，用于观测kruskal和prim算法的运行时间稀疏对称矩阵采用如下方法生成a=ones(300)*1000;% 如果 a(i,j)=1000 表明 i,j 两点不连通a(:,2)=ceil(50*ra nd(1,300);a(2,:)=a(:,2)'a(1,3)=1;a(3,1)=1;a(4,8)=2;a(8,4)=1;for ii

25、=1:300a(ii,ii)=0;%(for prim )end这是一个多播网，2号结点是广播源，1, 3结点和2相连外，还彼此相连，同理4,8结点。运行结果如下：a. Primlease input the point vhere you want to start f do renieMber it must bs tetveen 1 sni iOO 5 Elapsed t inie Ls 0. 1*83300 seconds.录I住删时总曲既7337b. kruskalElapsed tme is 二.t>09000 seconds. 最小柱我树的总ft价为73373. 结果对比(

26、时间单位seco nds)J稀疏图稠密图Prim0.1880.172Kruskal3.60922.719从表格的行的方向对比说明：prim算法更适于处理稠密图；kruskal算法更适于处理稀疏图。从表格的列的方向对比说明：似乎是prim算法在两种场合都优于kruskal算法，但这个结论是不正确的，因为我的kruskal算法还没有达到最优化。(2)从降低内存消耗、减少计算时间的角度，对算法进行优化。1. prim算法对于prim算法，我认为在我的思路范围内已经达到了最优。尤其得意的是寻找非零最小值的代码实现，认为很具有matlab风格。k=lowcost>0;%k 为一逻辑数组，它和low

27、cost同维，对于每一个位置i if lowcost(i)>0 贝U k(i)=1%否则k(i)=0;稍候将用这个数组进行辅助寻址cost_min=min(lowcost(k);%找出 lowcost 中除 0 外的最小值in dex=fi nd(lowcost=cost_mi n);%找出此最小值在lowcost 中的下标，即找到相应的节点in dex=in dex(1);%因为最小值的下标可能不止一个，这里取第一个下标进行处理lowcost(i ndex)=0;%表明该节点已经加入了最小生成树中2. Kruskal 算法对Kruskal算法，我有两点优化ur 沪Wi；心ii孤址翩瞰阿

28、ia能八瘀阳忙胡.弓料尸-亠爭F評Hi滸益；於亦哎占冼狀两讯胡吏更無!匸|#11.3 (?4K：z«dE!fl (hn-Js ' - - O' _晅更竺迦嗣侖制WJ咖'惦甜縣，皑課H应惦ten)列确 rw：_iijn=icn(TU, ：) £吏出；'电手,fjjjinds-f ini IT 1 h; «st Jiifli) 盯二柚F"Viratazitdii;m麵mm為 联風他厠购m,期柯方srn 删£丁酣甜新aIhKklTOlLt-I uM;馳 i；旷 m* 附潇验血號匪阳虑站5九诚加中刖幅比追騙雄tenz :

29、nrjdeL an:thiipttnrt'-();leu(arjotj*eij):mE, indei'-JEC.1甲和护血估凹卅)吕如冋刖"兰"'刊I i-Esfl-即 ¥2.咖堆4埔Ol邸杠eijHi,JwtLtcpjirA J”冃匸;寻.三寸审工早_1=1+工下耐01社巧姑确叶從*建劉之掘-馆託養即:町7fci j-l；leniih.deL诃：三IE卜屯if<址咚(jJ =t叩Sturtbrapoiirt>JUjTnirttsepoiit)E馥tigWr 弟ffflmntherpBii*峠伯变RindBiEll:理fflt

30、厲:=t 驾injei);endC/4WElflt vtltai t smtlBTpiiiit' =t k firdu t;idf cmtteir Mi” 时：*5吏"etvi13 -j=F=lt比叫;11 -iHfETElCeir?!-!. I u)1515-ir-：8 .20 -2125X0£-:T-2330-J5-A -E”nnm：T 7(1,:) :f :的苦一.、 nMiidCni, ;>=mtjii>馳“阳版血点 iii込 miTOfM诵 曲审删M湘酹TtffibSA妆酿1»脈 肺菠杯附斷鴉 inrflxijicuitiKlhZndsil, x?'2TE','.r-' r?開贬犯脚E貝我,l?lb翹i£l?申种耳戦5理畑、t包 iindni,SMlh吨 MJit凶 叫、t*HD I aidthtuflinr, i 於曲 l OP if (tat aixnliciDDiEit) *;lat 1泌!”1!雰专辭展千-i SOflt，切丰厭伽尬显小捕臨也sqm诚cfiJ- indo, mtflbEqiniiil LMM.' Jt:-Fi：歆紀農肝卜坐哉談，一蛙旺棗thnulHsfn