matlab kruskal算法

Kruskal算法是另一种常用的解决最小生成树问题的算法。在MATLAB中，你可以使用以下代码来实现Kruskal算法：

function MST = kruskalAlgorithm(graph)
    numNodes = size(graph, 1);
    numEdges = nnz(graph) / 2;
    
    % 创建边集合
    edges = [];
    for i = 1:numNodes
        for j = i+1:numNodes
            if graph(i, j) > 0
                edges = [edges; i, j, graph(i, j)];
            end
        end
    end
    
    % 对边按权值进行排序
    sortedEdges = sortrows(edges, 3);
    
    % 初始化并查集
    parent = 1:numNodes;
    rank = zeros(1, numNodes);
    
    % 初始化最小生成树
    MST = zeros(numNodes);
    
    % 遍历边集合，选择权值最小的边并判断是否构成环
    for i = 1:numEdges
        u = sortedEdges(i, 1);
        v = sortedEdges(i, 2);
        w = sortedEdges(i, 3);
        
        if find(parent, u) ~= find(parent, v)
            MST(u, v) = w;
            MST(v, u) = w;
            union(parent, rank, u, v);
        end
    end
end

function root = find(parent, x)
    if parent(x) ~= x
        parent(x) = find(parent, parent(x));
    end
    root = parent(x);
end

function union(parent, rank, x, y)
    rootX = find(parent, x);
    rootY = find(parent, y);
    
    if rank(rootX) < rank(rootY)
        parent(rootX) = rootY;
    elseif rank(rootX) > rank(rootY)
        parent(rootY) = rootX;
    else
        parent(rootY) = rootX;
        rank(rootX) = rank(rootX) + 1;
    end
end

这段代码实现了Kruskal算法，其中`graph`是一个邻接矩阵，表示图的连接关系。函数返回一个最小生成树的邻接矩阵MST。请注意，此代码假设图是连通的。如果图不连通，你可能需要进行额外的处理。