II . 用Krusal算法(避圈法)求最小生成树.doc

(避圈法),程序设计Kruskal算法的基本思想是:设无向连通网为G=(V,E),令G的最小生成树为T=(U,TE),其初始状态为U=V,TE={},这样T中各顶点各自构成一个连通分量。然后按照边的权值由小到大的顺序,依次考察边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量,则将此边加入到TE中去,同时把两个连通分量连接成一个连通分量;若被考察边的两个结点属于同一个连通分量,则舍去此边,以免造成回路,如此下去,当T中的连通分量个数为1时,此连通分量便为G的一棵最小生成树。显然,Kruskal算法实现起来要比prim算法复杂些。选择合适的存储结构存储图,采用合适的排序算法对程序执行效率的提高非常重要,采用简单而明了的方法判断边的两个端点是否在一个连通分支上更是尤为重要。一般来说,涉及Kruskal算法多采取边集数组做为图的存储结构,但考虑到matlab不像C语言那样可以方便地动态的生成数组和释放内存,仍采取了邻接矩阵的形式保存图,用于测试的两幅图,,.(注:邻接矩阵的对角线元素设定为100)这样既方便对边进行操作,又方便对边的顶点进行操作。使用邻接矩阵容易引起的问题是:由于邻接矩阵是对称矩阵,比如graph_adjacent(1,2)和graph_adjacent(2,1)代表的是同一条边,所以当有一条边被选入最小生成树后,要对它的两个结点分别进行更新。整个程序是以顶点为基本单位处理的。由于一条边对应两个结点,取标号较小的顶点做为主要处理对象,并用它来寻址该边所对应的另一个结点。这样规格化的好处在于:程序流程的每一步都会在自己的预测中,出现了错误易于查找。下面介绍一下一个matlab的built_in排序函数sort这个函数的功能非常强,也正因为采用了这个函数才使我的程序简洁高效。[Y,I]=sort(A);其中A为矩阵。则Y为将A中各列按从小到大排序后的结果,I为Y中的元素在原矩阵A中所在的行号。举例如下对于判断两个点是否在同一个连通分支,我的方法如下:声明一数组tag保存每个结点所在的连通分支的标号,初始值为每个结点的标号,当两个连通分量相连后则将它们的tag值设为一致程序流程图:关键代码说明:如何判断两个点是否在同一个连通分支①将图中每个顶点的tag值设为自身标号forj=1:lentag(j)=j;%关联标志初始化,将每个顶点的关联标志设为其本身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)==tag(anotherpoint))&(j~=anotherpoint))%遍搜tag数组,先将和anotherp