克鲁斯卡尔算法求解最小生成树：处理多个根节点

克鲁斯卡尔算法是一种用于求解最小生成树的贪心算法，适用于无向连通图。当图中存在多个根节点时，可以使用克鲁斯卡尔算法求解最小生成森林。

算法流程如下：

1. 将图中的边按照权值从小到大排序。
2. 遍历每一条边，如果这条边连接的两个节点不在同一连通分量中，则将这条边加入生成树中。
3. 重复步骤2，直到所有的节点都被加入生成树中或者所有的边都被遍历过。

MATLAB代码实现：

function [T, cost] = kruskal(G)
% G: 图的邻接矩阵
% T: 最小生成森林的邻接矩阵
% cost: 最小生成森林的权值和

[n, ~] = size(G);
% 将边按照权值从小到大排序
edges = [];
for i = 1:n
    for j = i+1:n
        if G(i,j) ~= 0
            edges = [edges; i, j, G(i,j)];
        end
    end
end
edges = sortrows(edges, 3);

% 初始化并查集
p = 1:n;
rank = zeros(1, n);

% 遍历每一条边
T = zeros(n,n);
cost = 0;
for i = 1:size(edges,1)
    u = edges(i,1);
    v = edges(i,2);
    w = edges(i,3);
    % 判断节点是否在同一连通分量中
    if find_set(u, p) ~= find_set(v, p)
        % 加入生成森林中
        T(u,v) = w;
        T(v,u) = w;
        cost = cost + w;
        % 合并连通分量
        p = union_set(u, v, p, rank);
    end
end

function root = find_set(u, p)
% 查找节点所在的连通分量
root = u;
while root ~= p(root)
    root = p(root);
end
while u ~= root
    t = p(u);
    p(u) = root;
    u = t;
end

function p = union_set(u, v, p, rank)
% 合并连通分量
u = find_set(u, p);
v = find_set(v, p);
if rank(u) > rank(v)
    p(v) = u;
else
    p(u) = v;
    if rank(u) == rank(v)
        rank(v) = rank(v) + 1;
    end
end

该算法的时间复杂度为$O(ElogE)$，其中E为边的数量。