mintree.m

这是关于图论的源代码和ppt的讲解

function b=mintree(w)
n=length(w);
leng=0;

d=1000;jj=1;
for j=2:n
    if(w(1,j)<d)
        d=w(1,j);
        jj=j;
    end
end
leng=leng+w(1,jj);
w(1,jj)=1000;
w(jj,1)=1000;
b=[1,jj];

for k=1:n-2
    x=1000+zeros(n,n);
    m=length(b);
    for i=1:n
        for j=1:m
            x(i,b(j))=w(i,b(j));
            x(b(j),i)=w(b(j),i);
        end
    end
    
    d=1000;ii=1;jj=1;
    for i=1:n
        for j=1:n
            if(x(i,j)<d)
                d=x(i,j);
                ii=i;
                jj=j;
            end
        end
    end
    leng=leng+w(ii,jj);
    w(ii,jj)=1000; 
    w(jj,ii)=1000;
    b=[b,ii,jj];
    for j=1:m
        w(ii,b(j))=1000;
        w(b(j),ii)=1000;
        w(jj,b(j))=1000;
        w(b(j),jj)=1000;        
    end
end

b,leng