mintree.m

这是解决图论中最小树问题的求解程序

function [Wt,P]=mintree(W)
% W is the matrix of costs W(i,j), Wt is the least cost, P(:,1:2) are edges of the tree 
% P(:,3) are costs of the tree, P(:,4) is the index of the edges.
n=length(W(:,1));W=triu(W); W(find(W==0))=inf; P=zeros(n-1,4);
edgindex=find(W~=inf); % a column vector of index of nonzero and non-inf of W, the dim is the number of edges.
nE=length(edgindex); % nE is the number of edges. 
[b, c]=find(W~=inf); % [b(i),c(i)] is the edges, and b(i) < c(i)
edges=[b,c]; 
[cost,edge]=sort(W(edgindex)); % sort the costs of edges in increasing order
E=[edges(edge,:),cost,edge]; %the matrix of four columns: edge points, costs, and edges
P(1,:)=E(1,:); 
for k=1:n-2 
    M=max(E(1,2),E(1,1)); m=min(E(1,2),E(1,1));
    E(find(E(:,1)==M),1)=m;
    E(find(E(:,2)==M),2)=m;
    E=E(find(E(:,1)-E(:,2)),:); % delete the selected edge and the edges that will form cycles.
    P(k+1,:)=E(1,:); 
end;
Wt=sum(P(:,3));
% output edges of least tree
P(:,1:2)=edges(P(:,4),:);
for k = 1:n-1
    disp(['    ','e', num2str(P(k,4)), '  ', '(v', num2str(P(k,1)),'  ','v', num2str(P(k,2)), ')']);
end;
% draw picture of the least cost tree 
axis equal; hold on; [x,y]=cylinder(1,n); xm=min(x(1,:)); ym=min(y(1,:)); xx=max(x(1,:)); yy=max(y(1,:));
axis([xm-abs(xm)*0.15, xx+abs(xx)*0.15, ym-abs(ym)*0.15, yy+abs(yy)*0.15]);
plot(x(1,:),y(1,:),'ko')
for k = 1:n % draw points
    temp=['  v', int2str(k)];
    text(x(1,k),y(1,k),temp);
end
for k = 1:nE, plot(x(1,edges(k,:)),y(1,edges(k,:)),'b'); end  % draw edges in blue
for k=1:n-1 plot(x(1,P(k,1:2)),y(1,P(k,1:2)),'r');end; % draw least tree in red
text(-0.35,-1.2,['The least cost of spanning tree is', '   ',num2str(Wt)]);
title('The economical spanning tree is in red'); axis('off'); hold off;