最小生成树(强烈推荐).doc

%==========================================================================
%相关概念:
% 1、给定一个图G=(V,E),如果它不含任何回路,就称它为林;如果G又是连通的,即
%这个林只有一个连通支,就称它为树。
% 2、树中的边称为树枝,度为1的结点称为树叶。
% 3、树的每条边都不属于任何回路,这样的边称为割边。
% 4、树中一定存在树叶结点。
%==========================================================================
%实际意义:
% 最小支撑树问题:任意两个结点之间都有通路,且所有边的长度之和最小。
%==========================================================================
%算法及步骤:
% Kruskal算法,属于贪心算法。
% 时间复杂度为O(M+p*logM),p为迭代次数。
% 无向图:选取最短的边,若形成回路则删除最长边;直至选取N-1条为止。
% 有向图:先判断是否为发点(只有出度而没有入度),若不是发点则寻找从发点到达该
%点的路径。
%==========================================================================
%输出结果:
% 最小支撑树(林)的边列表。
%==========================================================================
%输入边列表D
order; %将各条边按长度从小到大排列
m=0; %记录已选边数
C_tree=[]; %结果的权矩阵
D_tree=[]; %结果的边列表
if isDiagraph==0 %无向图
i=1; %记录待选边号
while i<=M & m<N-1 %N为结点数,M为边数
C_tree(D(i,1),D(i,2))=D(i,3);
C_tree(D(i,2),D(i,1))=D(i,3);
if FindCircle(C_tree,0)==1 %若构成回路,则删除最新加入的边
C_tree(D(i,1),D(i,2))=0;
C_tree(D(i,2),D(i,1))=0;
else %若未构成回路
m=m+1;
D_tree(m,:)=D(i,:);
end;
i=i+1;
end;
else %有向图
end_at=zeros(1,N); %记录结点的入度
AIM=1:N