Kruskal算法的MATLAB实现.doc

发布时间：2022-05-31 发布人：admin 分类：说明书资料大小：0.02M 资料格式：doc 举报版权申诉

qq_25832821-10230482-16359647414653822442.doc.pdf-第1页.png

第1页 / 共3页

qq_25832821-10230482-16359647414653822442.doc.pdf-第2页.png

第2页 / 共3页

qq_25832821-10230482-16359647414653822442.doc.pdf-第3页.png

第3页 / 共3页

文本预览

Kruskal 算法的 matlab 实现郑浩东程序： function [T,a]=Kruskal(d) %输入参数 d 是原图的权值矩阵；输出参数 T 是最小生成树的顶点组成的矩阵，每条边的两个顶点放在同一列中；a 是最小生成树的总权值 n=length(find(d~=0&d~=inf))/2; b=zeros(3,n); %用于存放原图的边的顶点以及边的权值 k=1; for i=1:length(d) 列中 %将原图的边的顶点与权值放入 b 中，同一条边的顶点与权值放在同一 %找到原图的总边数 for j=i+1:length(d) if d(i,j)~=0&&d(i,j)~=inf b(1,k)=i; b(2,k)=j; b(3,k)=d(i,j); k=k+1; end end end b=sortrows(b',3)'; %将 b 中的各列按边的权值从小到大进行重新排列 m=max(b(3,:)); a=0; T=[]; t=1:length(d); kk=1; for i=1:n 似运用了并查集算法的思想 %给予顶点标号 %该循环中包含在生成树时防止形成环的程序，以及找出最小生成树；防止形成环貌 if t(b(1,i))~=t(b(2,i)) %判断选取的边是否会与已选取的边形成环，不会就继续选取 T(1,kk)=b(1,i); T(2,kk)=b(2,i); a=a+b(3,i); kk=kk+1; tmin=min(t(b(1,i)),t(b(2,i))); tmax=max(t(b(1,i)),t(b(2,i))); for ii=1:length(d) if t(ii)==tmax t(ii)=tmin; %改变已选取的边的顶点的标号

end end end if kk==m break; end end T a end 执行： >> d(1,:)=[0,2,inf,inf,inf,4,inf];d(2,:)=[zeros(1,2),4,inf,inf,5,inf];d(3,:)=[zeros(1,3),8,inf,3,7];d(4, :)=[zeros(1,4),inf,inf,8]; d(5,:)=[zeros(1,5),3,7];d(6,:)=[zeros(1,6),6];d(7,:)=zeros(1,7);d=d+d';[T,a]=Kruskal(d); T = a = 1 2 3 6 5 6 1 6 6 7 3 4 26

注：ppt 中的 Kruskal 算法程序存在错误，如果像 ppt 那样输入参数为原图的顶点与权值组成的矩阵 b，那么程序前半部分大部分是多余无意义的；如果输入参数是原图的权值矩阵，程序会出错，无法运行，且也存在多余的步骤。

分享到：

赞收藏

资料库

Kruskal算法的MATLAB实现.doc

相关推荐

人工智能

热门标签

最新资料