kruskal.m

Kruskal求最小生成树算法 . 详细中文注释, 易于理解!

% kruskal.m  
% Kruskal求最小生成树算法  
% 作者: 杨建栋%
% 日期: 2009年1月11日%
% 输入参数:  PV = nx3 矩阵. 第一列和第二列定义边 (2个节点),第三列为边权值
% 输出参数: w = 最小生成树权值
%         T = 最小生成树邻接矩阵
%----------------------------------------------------
function [w,T] = kruskal(PV)
row = size(PV,1)
X = [];
% 根据输入矩阵PV,创建邻接矩阵
for i = 1 : row
    X(PV(i,1),PV(i,2)) = 1;
    X(PV(i,2),PV(i,1)) = 1;
end
X
% 把矩阵PV按第3列(边权值)重新排序(升序).
PV = fysalida(PV,3);
% 取邻接矩阵的行数,即节点个数
n = size(X,1);
% 以下数组为n(n为节点数)维数组,初始化为0(未标记),非0则表示该节点已标记.
korif = zeros(1,n);
% 从权值最小的边开始加入,直至最大边.
for i = 1 : row    
    akmi = PV(i,[1 2]);
    % 判断插入边[i,j]后,是否会使图循环.
    [korif,c] = iscycle(korif,akmi);
    % 如果插入边[i,j]后产生循环,则在矩阵PV中将此边对应行改为[0 0 0]
    if c == 1
       PV(i,:) = [0 0 0];
   end
end
% 计算最小生成树权值
w = sum(PV(:,3)');
% 创建最小生成树对应的邻接矩阵
T = zeros(n);
for i = 1 : row
    if PV(i,[1 2]) ~= [0 0]
        T(PV(i,1),PV(i,2)) = 1;
        T(PV(i,2),PV(i,1)) = 1;
    end
end