kruskal.m

来自「prim算法 kruskal算法用matlab实现 输入标准：x邻接矩阵 p」· M 代码 · 共 45 行

function [g,l]=kruskal(x,p)
%x is the adjancing matrix
%p is the set of the point
%g is the sets of groups of points connected to each other
%l is the sets that have the min length and connect separate groups

for i=1:length(p)
 g(i,:)=[i linspace(0,0.9,length(p))];
end
l=[];

lmin_st=0;
lmin_en=0;
%record the 2 group connect toeach other in every step
ii_r=0;
jj_r=0;
%choose length(p)-1 paths
for num=1:length(p)-1 
 lmin=inf;
 %choose different connected groups and find the shortest path
    for ii=1:length(p)-1
       for jj=ii+1:length(p)
          for m=1:find(g(ii,:)==0)-1
             for n=1:find(g(jj,:)==0)-1 
              if lmin>x(g(ii,m),g(jj,n))
              lmin=x(g(ii,m),g(jj,n));
              lmin_st=g(ii,m);
              lmin_en=g(jj,n);
              ii_r=ii;
              jj_r=jj;
              end 
             end
          end
        end
    end
    %adjust g
  %connect two connected groups into one  
 g(ii_r,[find(g(ii_r,:)==0):find(g(ii_r,:)==0)+find(g(jj_r,:)==0)-1])=g(jj_r,[1:find(g(jj_r,:)==0)]);
  %eliminate group jj_r;
 g(jj_r,:)=zeros(1,length(p)+1);
  %add new side into l sets
  l=[l [lmin_st lmin_en]];
end