最小生成数 克鲁斯卡尔 普里姆 matlab

克鲁斯卡尔：

function   T=MST_Kruskal(G)

n=0;

if  isfield(G,'w')  && ~isempty(G.w)  &&  size(G.w,1)==size(G.w,2)

    W=G.w;n=size(W,1);

end

if  isfield(G,'e')  && ~isempty(G.e)  && size(G.e,2)==3

    E=G.e;  n=max(max(E(:,1:2));

elseif n==0

    error('incorrect input argument');

else

    E=[];

    for i=1:n

    for j=i+1:n

        if W(i,j)~=0  &&  W(i,j)~=inf

            E=[E;  i  j  W(i,j)];

        end

    end

    end

end

T=[];

m=0;

C=1:n;

while  m<n-1  &&  ~isempty(E)

    e=E(:,3);

    [minW, ind]=min(e);

    v1=E(ind,1);

    v2=E(ind,2);

    if  C(v1)~=C(v2)

        T=[T; E(ind,:)];

        m=m+1;

        C(C==C(v2))=C(v1);

    end

    E(ind,:)=[];

end

　　普里姆：

function   T=MST_Prim(G)

n=0;

if  isfield(G,'w')  && ~isempty(G.w)  &&  size(G.w,1)==size(G.w,2)

    W=G.w;n=size(W,1);

end

if  isfield(G,'e')  && ~isempty(G.e)  && size(G.e,2)==3

    E=G.e;  n=max(max(E(:,1:2));

elseif n==0

    error('incorrect input argument');

else

    E=[];

    for i=1:n

    for j=i+1:n

        if W(i,j)~=0  &&  W(i,j)~=inf

            E=[E;  i  j  W(i,j)];

        end

    end

    end

end

V=1:n;

U=[1];  V=setdiff(V,U);

T=[];

while  length(U)<n

    EUV=[];

    for k=1:size(E,1)

        if  ismember(E(k,1), U) && ismember(E(k,2), U) ||  ~ismember(E(k,1), U) &&  ~ismember(E(k,2), U)

        else

            EUV=[EUV; E(k,:)];

        end

    end

    e=EUV(:,3);

    [minW  ind]=min(e);

    v1=EUV(ind,1);

    v2=EUV(ind,2);

    if  ismember(v1,U)

        U=[U, v2];

    else

        U=[U, v1];

    end

    T=[T; v1 v2 minW];

end