最小生成树kruskal算法matlab代码

最小生成树Kruskal算法是一种常用的图论算法，用于找到一个连通图的最小生成树。下面是Kruskal算法的MATLAB代码示例：

function [MST, totalWeight] = kruskalAlgorithm(adjMatrix)
    numNodes = size(adjMatrix, 1);
    edges = [];
    for i = 1:numNodes
        for j = i+1:numNodes
            if adjMatrix(i, j) > 0
                edges = [edges; i, j, adjMatrix(i, j)];
            end
        end
    end
    
    edges = sortrows(edges, 3); % 按边的权重升序排序
    
    parent = 1:numNodes;
    rank = zeros(1, numNodes);
    
    MST = zeros(numNodes-1, 2);
    totalWeight = 0;
    count = 0;
    
    for i = 1:size(edges, 1)
        u = edges(i, 1);
        v = edges(i, 2);
        weight = edges(i, 3);
        
        % 判断是否形成环路
        if findParent(u, parent) ~= findParent(v, parent)
            count = count + 1;
            MST(count, :) = [u, v];
            totalWeight = totalWeight + weight;
            
            % 合并两个集合
            union(u, v, parent, rank);
            
            if count == numNodes - 1
                break;
            end
        end
    end
end

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

function union(u, v, parent, rank)
    rootU = findParent(u, parent);
    rootV = findParent(v, parent);
    
    if rank(rootU) < rank(rootV)
        parent(rootU) = rootV;
    elseif rank(rootU) > rank(rootV)
        parent(rootV) = rootU;
    else
        parent(rootV) = rootU;
        rank(rootU) = rank(rootU) + 1;
    end
end

这段代码实现了Kruskal算法，输入参数`adjMatrix`是一个邻接矩阵，表示图的连接关系和权重。输出结果`MST`是最小生成树的边集合，`totalWeight`是最小生成树的总权重。