Kruskal算法寻找最小树的matlab程序.pdf

《Kruskal算法寻找最小树的matlab程序.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Kruskal算法寻找最小树的matlab程序functiontree=kruskal(d)%矩阵d为无向图的权矩阵，且是对称矩阵N=size(d,1);k=0;%记录图中边的条数I=max(max(d));%I作为无穷大edge=zeros(N*(N-1)/2,3);%用于存储图中所有的边，边的条数最多为n*(n-1)/2fori=1:N-1%因为权矩阵是对称阵，所以只用上三角矩阵。forj=i+1:Nifd(i,j)

2、的行。o_edge=edge;%用于存储排序后的边及边的端点。fori=1:k-1%用选择排序法进行升序排序forj=i+1:kifo_edge(i,3)>o_edge(j,3)temp=o_edge(i,:);o_edge(i,:)=o_edge(j,:);o_edge(j,:)=temp;endendendtree=zeros(N-1,3);%用于存放最小树中的边及边的端点，最小树中的边数为节点数减1tree(1:2,:)=o_edge(1:2,:);%两条边一定不能构成圈，所以前面最小的两条边一定在最小树中。line=3;fori=3:kifline==N%如果line=

3、N说明tree矩阵已填满，最小树已经找到，跳出循环break;elseifline

4、

5、isempty(find(tree(:,1:2)==o_edge(i,2),1))%判断tree中已经确定的的所有边中的节点是否和新增加的边的两个端点都重复，若新边的两个端点不都重复，则为真%直接说明新边符合条件，加入tree中。tree(line,:)=o_edge(i,:);line=line+1;else%否则，判断新边的加入是否会构成回路，若不会则说明新边仍符合要求，加入tree中，若构成回路，则

6、i加1，继续循环。ii=1:i;%ii数组用于存放除去端点仅出现一次的边后所剩余的边。while1%判断加入新边后是否有回路存在。fre=zeros(1,N);%用于记录加入新边后，各节点出现的次数。index=length(ii);%计算除去端点仅出现一次的边后所剩余的边的条数forj=1:index%计算剩余边中各端点出现的次数fre(o_edge(ii(j),1))=fre(o_edge(ii(j),1))+1;fre(o_edge(ii(j),2))=fre(o_edge(ii(j),2))+1;endonce=find(fre==1);%记录仅出现一次的节点标号cou

7、nt=0;%用于计数两个端点均出现两次或两次以上的边的条数more=zeros(1,index);%记录两个端点均出现两次或两次以上的边form=1:indexifisempty(find(once==o_edge(ii(m),1),1))&&isempty(find(once==o_edge(ii(m),2),1))%判断各边的两个端点中是否有仅出现一次的端点；若没有，则条件为真count=count+1;more(count)=ii(m);endendifcount==index&&count~=0%如果count和index相等且count不等于0，说明剩余的边构成了回路

8、break;elseifcount==0%如果count==0说明新边的加入没有构成回路，故将新边加入tree。tree(line,:)=o_edge(i,:);line=line+1;breakelseii=more(1:count);%如果count不等于index，则说明说明前i条边中的存在仅出现一次的节点，因此将含这些节点的边删除。endendendendend