MATLAB解决kruskal求最小生成树

Kruskal算法是一种用来寻找加权无向图的最小生成树的算法。其基本思想是按照边的权重顺序（从小到大）选择边，并保证这些边不会形成环，直到连接所有顶点形成树为止。以下是使用MATLAB实现Kruskal算法的基本步骤：

1. 将所有的边按照权重从小到大排序。
2. 初始化一个空的最小生成树。
3. 遍历排序后的边列表，对于每条边，如果它连接的两个顶点在最小生成树中不构成环，就将它加入到最小生成树中。
4. 当最小生成树中包含所有顶点时，算法结束。

在MATLAB中，可以使用以下代码框架来实现Kruskal算法：

function mst = kruskalAlgorithm(adjMatrix)
    [numNodes, ~] = size(adjMatrix); % 获取顶点数
    mstEdges = []; % 最小生成树的边
    parent = 1:numNodes; % 初始化每个节点的父节点为自己，表示每个节点自成一棵树

    % 将所有边按权重排序，并存储到数组中，格式为[weight, u, v]
    edges = [];
    for u = 1:numNodes
        for v = u+1:numNodes
            if adjMatrix(u, v) > 0 % 如果u和v之间有边
                edges = [edges; adjMatrix(u, v), u, v];
            end
        end
    end
    edges = sortrows(edges, 1); % 按权重排序

    % Kruskal算法主循环
    for k = 1:size(edges, 1)
        weight = edges(k, 1);
        u = edges(k, 2);
        v = edges(k, 3);
        uRoot = findRoot(parent, u);
        vRoot = findRoot(parent, v);
        % 如果u和v不在同一个子集中，将它们合并
        if uRoot ~= vRoot
            mstEdges = [mstEdges; weight, u, v];
            parent(uRoot) = vRoot; % 路径压缩
        end
        % 如果最小生成树已经有numNodes-1条边，则已构成最小生成树
        if size(mstEdges, 1) == numNodes - 1
            break;
        end
    end
    % 提取最小生成树的边的权重
    mst = edges(mstEdges(:, 1), 1);
end

function root = findRoot(parent, node)
    % 查找节点的根节点
    while parent(node) ~= node
        node = parent(node);
    end
    root = node;
end

使用这个函数时，需要传入一个邻接矩阵`adjMatrix`，表示图中各个顶点之间的连接和权重。函数返回的`mst`是一个包含最小生成树所有边权重的向量。