Prim算法和Kruskal算法地Matlab实现

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

2、 26v 79 224311834214622v 316 3011419155v 1v 664352016v 45v 57448（ 4）分析两种算法的实现复杂度。二 . 扩展要求：（ 1）提供对算法效率（复杂度）进行评估的方法，并通过举例验证，与分析得到的算法复杂度结果相对照；（ 2）从降低内存消耗、减少计算时间的角度，对算法进行优化。三实验步骤I. 用 Prim 算法求最小生成树i 算法分析及需求分析，程序设计prim 算法的基本思想是：设G=（V， E）是一个无向连通网，令T=（ U， TE）是 G的最小生成树。 T 的初始状态为U=v0 （ v0） TE= ，然后重复执行下述操作：在所有

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

4、留从该顶点到U 中的各顶点的最短边，取候选边最短边集为 V-U 中的 n-k 个顶点所关联的n-k 条最短边的集合。 为表示候选最短边集，需设置两个一维数组 lowcostn和 adjvexn, 其中 lowcost用来保存集合V-U 中的各顶点与集合U中顶点的最短边的权值，lowcostv=0表示顶点v 已经加入最小生成树中；adjvex用来保存依附于该边在集合U 中的顶点。例如下式表明顶点和顶点之间的权值为wlowcosti=w;adjvexi=k;程序流程图关键代码说明：1 将用于验证算法正确性的两幅图用邻接矩阵的形式保存，分别保存为文件 Graph1.m,Graph2.m （ 注 ：

5、矩 阵 的 对 角 线 元 素 设 置 为 零 。） 并 在 主 程 序finallyprim中直接进行调用。2 在输入起点时应该给程序的阅读者就该图的顶点数作出提示，不然的话使用者很可能会输入越界下标。采取的方法如下len=length(graph_adjacent);%求图中有多少个顶点k=sprintf(pleaseinputthepointwhere you want tostart,do rememberit must be between 1 and %d ,len);start_point=input(k);%输入最小生成树产生起点文案大全实用标准文档采取了 sprintf格式化

6、字符串的方法，就避免了编程的人每次根据输入图的顶点数手动对提示作修改。效果如下：在对第一幅图进行算法验证时在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

7、中输出的清晰，使人一目了然，也使用了 sprintf 格式化字符串的方法，代码如下s=0;for ii=1:len-1k=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 次循环中，每次循环要完成以下三项

8、工作1. 找到最小边，（需要求 lowcost 数组的最小非零值， 因为 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)

9、;%因为最小值的下标可能不止一个，这里取第一文案大全实用标准文档个下标进行处理lowcost(index)=0;%表明该节点已经加入了最小生成树中采用这种方法不仅充分利用了matlab 的 built_in函数，还避免了自己编写代码 （循环 +判断 lowcostv是否为 0）来实现寻找不为零的最小值的麻烦，提高了代码执行的效率。2. 对 lowcost和 adjvex进行更新，即：设刚加入最小生成树的顶点为index ，比较对于 U-V 中的每个顶点 v: 比较 lowcost(v) 和（ v，index ）边的权值大小，如果（ v， index ）边的权值小，则令 lowcost(v) 的

10、值为该边的权值，并将 adjvex(v) 的值等于 indexfor j=1:lenif lowcost(j)graph_adjacent(j,index);lowcost(j)=graph_adjacent(j,index);adjvex(j)=index;endend3. 将该边保存 tree(i,:)=adjvex(index),index;ii. 结果如下求第一张图的最小生成树：文案大全实用标准文档求第二张图的最小生成树：II .用 Krusal 算法（避圈法）求最小生成树i 算法分析及需求分析，程序设计Kruskal算法的基本思想是：设无向连通网为G=（ V， E），令 G的最小生成

11、树为T=（ U，TE），其初始状态为U=V，TE=, 这样 T 中各顶点各自构成一个连通分量。然后按照边的权文案大全实用标准文档值由小到大的顺序， 依次考察边集 E 中的各条边。 若被考察的边的两个顶点属于T 的两个不同的连通分量，则将此边加入到TE 中去，同时把两个连通分量连接成一个连通分量；若被考察边的两个结点属于同一个连通分量，则舍去此边，以免造成回路， 如此下去， 当 T 中的连通分量个数为 1 时，此连通分量便为G的一棵最小生成树。显然， Kruskal 算法实现起来要比prim 算法复杂些。选择合适的存储结构存储图，采用合适的排序算法对程序执行效率的提高非常重要，采用简单而明了的方

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

13、更新。整个程序是以顶点为基本单位处理的。由于一条边对应两个结点，取标号较小的顶点做为主要处理对象， 并用它来寻址该边所对应的另一个结点。这样规格化的好处在于： 程序流程的每一步都会在自己的预测中，出现了错误易于查找。下面介绍一下一个 matlab的 built_in排序函数 sort这个函数的功能非常强，也正因为采用了这个函数才使我的程序简洁高效。Y ， I=sort（ A）；其中 A 为矩阵。则 Y 为将 A 中各列按从小到大排序后的结果， I 为 Y 中的元素在原矩阵 A 中所在的行号。举例如下文案大全实用标准文档对于判断两个点是否在同一个连通分支，我的方法如下：声明一数组tag 保存每个

14、结点所在的连通分支的标号，初始值为每个结点的标号，当两个连通分量相连后则将它们的tag 值设为一致程序流程图：文案大全实用标准文档关键代码说明：1 如何判断两个点是否在同一个连通分支将图中每个顶点的tag 值设为自身标号for j=1:lentag(j)=j;%关联标志初始化，将每个顶点的关联标志设为其本身end;当确定两个顶点不在同一个连通分支时，将它们对应的边加入最优边集superedge 中，并修改其中一个顶点的及其所在连通分支的各个点的tag 值，使其和另一连通分支具有相同的tag 值。if(tag(anotherpoint)=tag(index)%当两个点不属于一个连通集时，这两个点

15、之间的边为最小生成树的边superedge(i,:)=index,anotherpoint;%将其加入最小生成树的边集中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(index);endendtag(anotherpoint)=tag(index);%将 anotherp

16、oint的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_min=min(Y(1,:);%找出权值最小的边index=f

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

18、的完成（ 1）提供对算法效率（复杂度）进行评估的方法，并通过举例验证，与分析得到的算法复杂度结果相对照；理论分析设图中的顶点数为 n，则 Prim 算法要执行 n-1 次外循环找齐最小边，每次外循环又要执行 n 次内循环对lowcost和 adjvex数组进行更新，所以Prim 算法的时间复杂度为O(),与网中的边数无关，因此适用于求稠密网的最小生成树。因为Kruskal算法是依次对图中的边进行操作，因此Kruskal算法的时间复杂度为O(e), 其中 e 为无向连通网中边的个数。相对Prim 算法而言， Kruskal算法适用于求稀疏网络的最小生成树。程序验证1 随机生成300 300 的对

19、称稠密矩阵，用于观测Kruskal和 Prim 算法的运行时间。（分别在finallyprim和 finallykruskal脚本文件中的主循环开始和结束为止加tic,toc）对称矩阵采用如下方法生成。a=ceil*(rand(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. primb. kruskal由此可见对于稠密图 prim 算法优于 kruskal 算法2 随机生成一稀疏对称矩阵，用于观测kruskal和 pr

20、im 算法的运行时间稀疏对称矩阵采用如下方法生成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;for ii=1:300a(ii,ii)=0;%（ for prim ）end这是一个多播网，2 号结点是广播源，1，3 结点和 2 相连外，还彼此相连，同理4，8 结点。运行结果如下：a.Primb. kruskal文案大全实用标准文档3. 结果对比 ( 时间单位 seconds)稀疏图稠密图Prim0.1880.172Kruskal3.60922.719从表格的行的方向对比说明：prim 算法更适于处理稠密图；kruskal算法更适于处理稀疏图。从表格的列的方向对比说明：似乎是 prim 算法在两种场合都优于 kruskal 算法，但这个结论是不正确的， 因为我的 kruskal 算法还没有达到最优化。（ 2）从降低内存消耗、减少计算时间的角度，对算法进行优化。1.prim 算法对于 prim 算法，我认为在我的思路范围内已经达到了最优。尤其得意的是寻找非零最小值的代码实现，认为很具有matlab 风格。k=lowcost0;%k为一逻辑数组， 它和 l