Prim算法和Kruskal算法的Matlab实现

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

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

3、算法的关键是如何找到连接U和V-U的最短边来扩充生成树T。设当前T中有k个点即T的顶点集U中有k个顶点那么所有满足uU，vV-U的边最多有k×(n-k)条，从如此大的边集中选取最短边是不太经济的。利用MST性质，可以用下述方法构造候选最小边集：对应V-U中的每个顶点，保存从该顶点到U中的各顶点的最短边，取候选边最短边集为V-U中的n-k个顶点所关联的n-k条最短边的集合。为表示候选最短边集，需设置两个一维数组lowcostn和adjvexn,其中lowcost用来保存集合V-U中的各顶点与集合U中顶点的最短边的权值，lowcostv=0表示顶点v已经参加最小生成树中；adjvex用来

4、保存依附于该边在集合U中的顶点。例如下式说明顶点vi和顶点vk之间的权值为wlowcosti=w;adjvexi=k;程序流程图关键代码说明：1 将用于验证算法正确性的两幅图用邻接矩阵的形式保存，分别保存为文件Graph1.m,Graph2.m注：矩阵的对角线元素设置为零。并在主程序finallyprim中直接进行调用。2 在输入起点时应该给程序的阅读者就该图的顶点数作出提示，不然的话使用者很可能会输入越界下标。采取的方法如下len=length(graph_adjacent);%求图中有多少个顶点k=sprintf('please input the point where you

5、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 and 7在对第二幅图进行算法验证时在workspace会有如下输出：ple

6、ase input the point where you want to start ,do remember it must be between 1 and 83 在输出结果时为了使结果在workspace中输出的清晰，使人一目了然，也使用了sprintf格式化字符串的方法，代码如下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=

7、s+graph_adjacent(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那么k(i)=1 %否那么k(i)=0;稍候将用这个数组进行辅助寻址co

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

9、x，比拟对于U-V中的每个顶点v:比拟lowcost(v)和v，index边的权值大小，如果v，index边的权值小，那么令lowcost(v)的值为该边的权值，并将adjvex(v)的值等于indexfor j=1:len if lowcost(j)>graph_adjacent(j,index); lowcost(j)=graph_adjacent(j,index); adjvex(j)=index; end end3.将该边保存tree(i,:)=adjvex(index),index;ii.结果如下求第一张图的最小生成树：求第二张图的最小生成树：II . 用Krusal算法避圈法

10、求最小生成树i算法分析及需求分析，程序设计Kruskal算法的根本思想是：设无向连通网为G=V，E，令G的最小生成树为T=U，TE，其初始状态为U=V，TE=,这样T中各顶点各自构成一个连通分量。然后按照边的权值由小到大的顺序，依次考察边集E中的各条边。假设被考察的边的两个顶点属于T的两个不同的连通分量，那么将此边参加到TE中去，同时把两个连通分量连接成一个连通分量；假设被考察边的两个结点属于同一个连通分量，那么舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。显然，Kruskal算法实现起来要比prim算法复杂些。选择适宜的存储结构存储图，采用适

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

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

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

14、,:)=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); end end tag(anotherpoint)=tag(index);%将anotherpoint的tag值变为index的tag值 en

15、d end注意：上面的红色代码局部，要先将连同分支的其他点的tag值变为tagindex，最后在改变taganotherpoint的tag值，如果先将tag(anotherpoint)的值改变了，编号在anotherpoint之后的点的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);%一条边对

16、应两个节点，且不同的边的权值可能一样，这里为了方便处理人为规定了顺序，取标号最小的顶点进行处理 anotherpoint=I(1,index);%找到该边对应的另一个顶点 %将该边对应的权值修改为最大，防止该边在下次循环中再次被选为最优边 temp(index,anotherpoint)=100;temp(anotherpoint,index)=100;3.显示模块采用的代码参见prim算法。ii.结果如下a 第一张图的最小生成树b 第二张图的最小生成树四扩展功能的完成1提供对算法效率复杂度进行评估的方法，并通过举例验证，与分析得到的算法复杂度结果相对照；理论分析 设图中的顶点数为n，那么Pr

17、im算法要执行n-1次外循环找齐最小边，每次外循环又要执行n次内循环对lowcost和adjvex数组进行更新，所以Prim算法的时间复杂度为O(n2),与网中的边数无关，因此适用于求稠密网的最小生成树。 因为Kruskal算法是依次对图中的边进行操作，因此Kruskal算法的时间复杂度为O(elog2e),其中e为无向连通网中边的个数。相对Prim算法而言，Kruskal算法适用于求稀疏网络的最小生成树。程序验证1 随机生成300×300的对称稠密矩阵，用于观测Kruskal和Prim算法的运行时间。分别在finallyprim和finallykruskal脚本文件中的主循环开始和

18、结束为止加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和prim算法的运行时间稀疏对称矩阵采用如下方法生成a=ones(300)*1000;%如果a(i,j)=1000说明i,j两点不连通a(:,2)=ceil(50*rand(1,300);

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