克鲁斯卡尔最小生成树算法 matlab实现

克鲁斯卡尔算法是一种用于求解最小生成树的算法，下面是一个用 Matlab 实现的示例代码：

function [MST, totalWeight] = KruskalMST(adjMatrix)
    n = size(adjMatrix, 1);
    edges = [];
    
    % 构建边集合
    for i = 1:n
        for j = i+1:n
            if adjMatrix(i, j) ~= 0
                edges = [edges; i, j, adjMatrix(i, j)];
            end
        end
    end
    
    % 按权重从小到大排序
    edges = sortrows(edges, 3);
    
    parent = 1:n;
    rank = zeros(1, n);
    MST = zeros(n-1, 2);
    totalWeight = 0;
    
    idx = 1;
    while idx <= size(edges, 1)
        u = edges(idx, 1);
        v = edges(idx, 2);
        w = edges(idx, 3);
        
        % 判断是否形成环路
        rootU = findRoot(parent, u);
        rootV = findRoot(parent, v);
        if rootU ~= rootV
            MST(idx, :) = [u, v];
            totalWeight = totalWeight + w;
            
            % 合并两个集合
            if rank(rootU) > rank(rootV)
                parent(rootV) = rootU;
            elseif rank(rootU) < rank(rootV)
                parent(rootU) = rootV;
            else
                parent(rootU) = rootV;
                rank(rootV) = rank(rootV) + 1;
            end
            
            idx = idx + 1;
        else
            % 舍弃该边，避免形成环路
            edges(idx, :) = [];
        end
    end
end

function root = findRoot(parent, node)
    while parent(node) ~= node
        parent(node) = parent(parent(node));
        node = parent(node);
    end
    root = node;
end

在上述代码中，`adjMatrix` 是一个邻接矩阵，表示图的连接关系和权重。`MST` 返回最小生成树的边集合，`totalWeight` 返回最小生成树的总权重。

注意：这只是一个简单的实现示例，实际应用中可能需要根据具体需求进行优化和修改。