matalb克鲁斯卡尔算法

克鲁斯卡尔算法是一种用于求解最小生成树的算法。它的基本思想是通过不断选择边来构建最小生成树，直到所有的顶点都被连接起来。下面是一个使用Matlab实现克鲁斯卡尔算法的例子：

function [MST, totalWeight] = kruskalAlgorithm(adjMatrix)
    numVertices = size(adjMatrix, 1);
    edges = [];
    for i = 1:numVertices
        for j = i+1:numVertices
            if adjMatrix(i, j) ~= 0
                edges = [edges; i, j, adjMatrix(i, j)];
            end
        end
    end
    edges = sortrows(edges, 3); % 按照边的权重进行排序
    
    MST = zeros(numVertices-1, 2);
    parent = 1:numVertices;
    rank = zeros(1, numVertices);
    totalWeight = 0;
    
    for i = 1:size(edges, 1)
        u = edges(i, 1);
        v = edges(i, 2);
        weight = edges(i, 3);
        
        [parent, rank] = union(u, v, parent, rank);
        
        if parent(u) ~= parent(v)
            MST(i, :) = [u, v];
            totalWeight = totalWeight + weight;
        end
    end
end

function [parent, rank] = union(u, v, parent, rank)
    uRoot = find(u, parent);
    vRoot = find(v, parent);
    
    if rank(uRoot) < rank(vRoot)
        parent(uRoot) = vRoot;
    elseif rank(uRoot) > rank(vRoot)
        parent(vRoot) = uRoot;
    else
        parent(vRoot) = uRoot;
        rank(uRoot) = rank(uRoot) + 1;
    end
end

function root = find(u, parent)
    while parent(u) ~= u
        u = parent(u);
    end
    root = u;
end

这个例子中，`adjMatrix`是一个邻接矩阵，表示图的连接关系和边的权重。函数`kruskalAlgorithm`使用克鲁斯卡尔算法来计算最小生成树，并返回最小生成树的边集合`MST`和总权重`totalWeight`。