mintree.m

无向图的最小生成树程序

function [Wt,T]=MINTREE(W)
% 无向图的最小生成树程序， W 是邻接矩阵，可以只有上三角的数据，且对角线上可以输入 0 或 inf, Wt 是最小树的权和, P是四个列向量组成的矩阵
% 其中 P(:,1:2) 是最小树的边, % P(:,3) 是最小树边的权, P(:,4) 是最小树的边在所有的边中按权从小到大排列的序号.
% T 是最小树由两个行向量组成, 上下行对应的是边.
n=length(W(:,1));W=triu(W); W(find(W==0))=inf; P=zeros(n-1,4);
edgindex=find(W~=inf); % 给图的所有的有限权的边编序号, 是列向量
[b, c]=find(W~=inf); % b, c 是列向量, [b(i),c(i)] 表示边,  b(i) < c(i)
edges=[b,c]; % 有限权的边的集合
[cost,edge]=sort(W(edgindex)); % 给图的所有的有限权的边按权从小到大排序， edge 是边对应的序号
E=[edges(edge,:),cost,edge]; %四列的矩阵，依次是，排序后的边(两列),对应的权, 对应的边序号
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)),:); % 删除会形成圈的边
    P(k+1,:)=E(1,:); 
end;
Wt=sum(P(:,3)); T=edges(P(:,4),:)';