Prim算法和Kruskal算法的Matlab实现.docx

Prim算法和Kruskal算法的Matlab实现计算机仿真期末大作业 Prim算法和Kruskal算法的Matlab实现 05605刘禹050697 连线问题应用举例： 欲铺设连接n个城市的高速公路，若i城与j城之间的高速公路造价为Cij，试设计一个线路图，使总的造价最低。 连线问题的数学模型就是图论中在连通的赋权图上求权最小的支撑树。试用Matlab分别实现求最小支撑数的Prim算法和Krusal算法。 一.基本要求： 画出程序流程图； 对关键算法、变量和步骤进行解释说明； 用如下两图对所写算法的正确性进行验证。即输入图的信息，输出对应图的最小支撑树及其权值。 v23v124v446v31523v7v6v591151426305724182520441661146319分析两种算法的实现复杂度。 8二.扩展要求： 提供对算法效率进行评估的方法，并通过举例验证，与分析得到的算法复杂度结果相对照； 从降低内存消耗、减少计算时间的角度，对算法进行优化。 三实验步骤 I.用Prim算法求最小生成树 i算法分析及需求分析，程序设计 prim算法的基本思想是：设G=是一个无向连通网，令T=是G的最小生成树。T的初始状态为U=v0TE=，然后重复执行下述操作：在所有uU， vV-U的边中找一条代价最小的边并入集合TE，同时v并入U，直至U=V为止。 显然，Prim算法的基本思想是以局部最优化谋求全局的最优化，而且，还涉及到起始结点的问题。 本程序完成的功能是：从图中的任意结点出发，都能够找出最小生成树 1 / 14 实现方案分析： Prim算法的关键是如何找到连接U和V-U的最短边来扩充生成树T。设当前T中有k个点则所有满足uU，vV-U的边最多有k条，从如此大的边集中选取最短边是不太经济的。利用MST性质，可以用下述方法构造候选最小边集：对应V-U中的每个顶点，保留从该顶点到U中的各顶点的最短边，取候选边最短边集为V-U中的n-k个顶点所关联的n-k条最短边的集合。为表示候选最短边集，需设置两个一维数组lowcostn和adjvexn,其中lowcost用来保存集合V-U中的各顶点与集合U中顶点的最短边的权值，lowcostv=0表示顶点v已经加入最小生成树中；adjvex用来保存依附于该边在集合U中的顶点。例如下式表明顶点和顶点之间的权值为w lowcosti=w; adjvexi=k; 程序流程图 关键代码说明： 1 将用于验证算法正确性的两幅图用邻接矩阵的形式保存，分别保存为文件Graph1.m,Graph2.m并在主程序finallyprim中直接进行调用。 2 在输入起点时应该给程序的阅读者就该图的顶点数作出提示，不然的话使用者很可能会输入越界下标。采取的方法如下 len=length(graph_adjacent);%求图中有多少个顶点 k=sprintf('please input the point where you want to start ,do remember it must be between 1 and %d ',len); 2 / 14 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会有如下输出： please input the point where you want to start ,do remember it must be between 1 and 8 3 在输出结果时为了使结果在workspace中输出的清晰，使人一目了然，也使用了sprintf格式化字符串的方法，代码如下 s=0; for ii=1:len-1 k=sprintf('最小生成树第%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.找到最小边， 由于是求非零的最小值，就不能在直接用min函数了。我采取的方法是这样的： k=lowcost>0;%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);%因为最小值的下标可能不止一个，这里取第一 3 / 14 个下标进行处理 lowcost(index)=0;%表明该节点已经加入了最小生成树中 采用这种方法不仅充分利用了matlab的built_in函数，还避免了自己编写代码来实现寻找不为零的最小值的麻烦，提高了代码执行的效率。 2.对lowcost和adjvex进行更新，即：设刚加入最小生成树的顶点为index， 比较对于U-V中的每个顶点v:比较lowcost(v)和边的权值大小，如果边的权值小，则令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.结果如下 求第一张图的最小生成树： 4 / 14 求第二张图的最小生成树： II . 用Krusal算法求最小生成树 i算法分析及需求分析，程序设计 Kruskal算法的基本思想是：设无向连通网为G=，令G的最小生成树为T=，其初始状态为U=V，TE=,这样T中各顶点各自构成一个连通分量。然后按照边的 5 / 14 权值由小到大的顺序，依次考察边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边加入到TE中去，同时把两个连通分量连接成一个连通分量；若被考察边的两个结点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。 显然，Kruskal算法实现起来要比prim算法复杂些。选择合适的存储结构存储图，采用合适的排序算法对程序执行效率的提高非常重要，采用简单而明了的方法判断边的两个端点是否在一个连通分支上更是尤为重要。 一般来说，涉及Kruskal算法多采取边集数组做为图的存储结构，但考虑到matlab不像C语言那样可以方便地动态的生成数组和释放内存，仍采取了邻接矩阵的形式保存图，用于测试的两幅图，分别保存为Graph11.M,Graph22.M.这样既方便对边进行操作，又方便对边的顶点进行操作。 使用邻接矩阵容易引起的问题是： 由于邻接矩阵是对称矩阵，比如graph_adjacent(1,2)和graph_adjacent(2,1)代表的是同一条边，所以当有一条边被选入最小生成树后，要对它的两个结点分别进行更新。整个程序是以顶点为基本单位处理的。由于一条边对应两个结点，取标号较小的顶点做为主要处理对象，并用它来寻址该边所对应的另一个结点。这样规格化的好处在于：程序流程的每一步都会在自己的预测中，出现了错误易于查找。 下面介绍一下一个matlab的built_in排序函数sort这个函数的功能非常强，也正因为采用了这个函数才使我的程序简洁高效。 Y，I=sort；其中A为矩阵。 则Y为将A中各列按从小到大排序后的结果，I为Y中的元素在原矩阵A中所在的行号。举例如下 6 / 14 对于判断两个点是否在同一个连通分支，我的方法如下： 声明一数组tag保存每个结点所在的连通分支的标号，初始值为每个结点的标号， 当两个连通分量相连后则将它们的tag值设为一致 程序流程图： 7 / 14 关键代码说明： 1 如何判断两个点是否在同一个连通分支 将图中每个顶点的tag值设为自身标号 for j=1:len tag(j)=j;%关联标志初始化，将每个顶点的关联标志设为其本身 end; 当确定两个顶点不在同一个连通分支时，将它们对应的边加入最优边集 superedge中，并修改其中一个顶点的及其所在连通分支的各个点的tag值，使其和另一连通分支具有相同的tag值。 if(tag(anotherpoint)=tag(index)%当两个点不属于一个连通集时，这两个点之间 的边为最小生成树的边 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); end end tag(anotherpoint)=tag(index);%将anotherpoint的tag值变为index的tag值 end end 注意：上面的红色代码部分，要先将连同分支的其他点的tag值变为tag，最后在改变tag的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);%找出权值最小的边对应的顶点 8 / 14 index=index(1);%一条边对应两个节点，且不同的边的权值可能一样，这里为了方便处理人为规定了顺序，取标号最小的顶点进行处理 anotherpoint=I(1,index);%找到该边对应的另一个顶点 %将该边对应的权值修改为最大，防止该边在下次循环中再次被选为最优边 temp(index,anotherpoint)=100; temp(anotherpoint,index)=100; 3.显示模块 采用的代码参见prim算法。 ii.结果如下 a 第一张图的最小生成树 b 第二张图的最小生成树 9 / 14 四扩展功能的完成 提供对算法效率进行评估的方法，并通过举例验证，与分析得到的算法复杂度结果相对照； 理论分析 设图中的顶点数为n，则Prim算法要执行n-1次外循环找齐最小边，每次外循环又要执行n次内循环对lowcost和adjvex数组进行更新，所以Prim算法的时间复杂度为O,与网中的边数无关，因此适用于求稠密网的最小生成树。 因为Kruskal算法是依次对图中的边进行操作，因此Kruskal算法的时间复杂度为O(e),其中e为无向连通网中边的个数。相对Prim算法而言，Kruskal算法适用于求稀疏网络的最小生成树。 程序验证 1 随机生成300300的对称稠密矩阵，用于观测Kruskal和Prim算法的运行时间。 对称矩阵采用如下方法生成。 a=ceil*(rand(300); b=triu(a); c=b; a=a+c; for ii=1:300 a(ii,ii)=0;%(for prim) or a(ii,ii)=1000%(for kruskal) end 运行结果如下： a. prim b. kruskal 由此可见对于稠密图prim算法优于kruskal算法 2 随机生成一稀疏对称矩阵，用于观测kruskal和prim算法的运行时间 10 / 14 稀疏对称矩阵采用如下方法生成 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:300 a(ii,ii)=0;% end 这是一个多播网，2号结点是广播源，1，3结点和2相连外，还彼此相连，同理4，8结点。 运行结果如下： a. Prim b. kruskal 3.结果对比(时间单位 seconds) Prim Kruskal 稀疏图 0.188 3.609 稠密图 0.172 22.719 从表格的行的方向对比说明： prim算法更适于处理稠密图；kruskal算法更适于处理稀疏图。 从表格的列的方向对比说明： 似乎是prim算法在两种场合都优于kruskal算法，但这个结论是不正确的，因为我的kruskal算法还没有达到最优化。 从降低内存消耗、减少计算时间的角度，对算法进行优化。 1.prim算法 11 / 14 对于prim算法，我认为在我的思路范围内已经达到了最优。尤其得意的是寻找非零最小值的代码实现，认为很具有matlab风格。 k=lowcost>0;%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);%因为最小值的下标可能不止一个，这里取第一个下标进行处理 lowcost(index)=0;%表明该节点已经加入了最小生成树中 2Kruskal 算法 对Kruskal算法，我有两点优化 修改后的代码如下： 12 / 14 修改后的代码更加充分的利用了matlab语言的特性，和其built_in函数。 用修改后的Kruskal算法分别求图1，图2的最小生成树结果如下 图一： 图二： 结果正确，说明改进后的Kruskal算法正确 用改进后的Kruskal算法求上面两个测试算法时间复杂度的图的最小生成树结果如下 a. 稠密图 13 / 14 b. 稀疏图 和prim算法时间对比如下 Prim kruskal 稀疏图 0.188 0.203 稠密图 0.172 0.063 这就很好的验证了结论：Prim算法更适用于稠密图；Kruskal算法更适用于稀疏图。 五.实验总结 经过一个学期的对matlab语言的学习和应用，已经能够熟练地使用matlab来编程和仿真，对这次程序的代码感到特别满意。因为充分利用了matlab语言的特性，使代码非常紧凑和简练，如果这两个算法用C语言实现的话，代码一定会比现在的复杂很多。 14 / 14