kruskal算法matlab程序

Kruskal算法是一种经典的最小生成树算法，用于在加权无向图中找到一棵最小的生成树。该算法主要分为以下三个步骤：

1. 初始化：将所有边按照权值从小到大排序。
2. 构建最小生成树：遍历每一条边，如果这条边的两个端点不在同一个集合中，就将它们加入到同一个集合中，并将这条边加入最小生成树中。
3. 输出最小生成树：输出步骤2中得到的最小生成树。

下面是Kruskal算法的Matlab程序实现，假设图用邻接矩阵表示，边用结构体表示：

function [T, w] = Kruskal(G)
    n = size(G,1);
    E = [];
    for i=1:n
        for j=i+1:n
            if G(i,j)>0
                E = [E; struct('u',i,'v',j,'w',G(i,j))];
            end
        end
    end
    E = sortrows(E,'w');
    T = zeros(n-1,2);
    S = DisjointSet(n);
    count = 0;
    for i=1:size(E,1)
        u = E(i).u;
        v = E(i).v;
        if S.Find(u)~=S.Find(v)
            S.Union(u,v);
            count = count+1;
            T(count,:) = [u v];
            if count==n-1
                break;
            end
        end
    end
    w = sum(G(sub2ind([n n],T(:,1),T(:,2))));
end

function S = DisjointSet(n)
    S.Parent = 1:n;
    S.Rank = zeros(1,n);
    S.Find = @Find;
    S.Union = @Union;
end

function [p, S] = Find(x, S)
    if x ~= S.Parent(x)
        S.Parent(x) = Find(S.Parent(x), S);
    end
    p = S.Parent(x);
end

function S = Union(x, y, S)
    [px, S] = Find(x, S);
    [py, S] = Find(y, S);
    if px == py
        return;
    end
    if S.Rank(px) < S.Rank(py)
        S.Parent(px) = py;
    elseif S.Rank(px) > S.Rank(py)
        S.Parent(py) = px;
    else
        S.Parent(py) = px;
        S.Rank(px) = S.Rank(px) + 1;
    end
end

该程序首先将图转化为边集，并按照边权值从小到大排序。然后，使用并查集数据结构来实现集合的合并操作，并依次遍历每一条边，如果这条边的两个端点不在同一个集合中，就将它们加入到同一个集合中，并将这条边加入最小生成树中。最后输出得到的最小生成树和它的权值。