导入坐标点，使用Prim算法求解最小生成树MT 用matlab将MT分解为n'棵子树

由于没有给出具体的坐标点，以下代码中的坐标点均为随机生成。

首先，我们需要导入坐标点，这里我们随机生成10个坐标点。

% 随机生成10个坐标点
n = 10;
points = rand(n, 2);

接下来，我们使用Prim算法求解最小生成树MT。

% 构造邻接矩阵
W = zeros(n);
for i = 1:n
    for j = i+1:n
        W(i, j) = norm(points(i,:) - points(j,:));
        W(j, i) = W(i, j);
    end
end

% Prim算法求解最小生成树MT
MT = zeros(n);
visited = false(n, 1);
visited(1) = true;
for k = 1:n-1
    minW = Inf;
    minI = -1;
    minJ = -1;
    for i = 1:n
        if visited(i)
            for j = 1:n
                if ~visited(j) && W(i, j) < minW
                    minW = W(i, j);
                    minI = i;
                    minJ = j;
                end
            end
        end
    end
    MT(minI, minJ) = minW;
    MT(minJ, minI) = minW;
    visited(minJ) = true;
end

最后，我们将MT分解为n'棵子树。

% 将MT分解为n'棵子树
visited = false(n, 1);
visited(1) = true;
child = zeros(n, 1);
for i = 2:n
    minW = Inf;
    minJ = -1;
    for j = 1:n
        if visited(j)
            for k = 1:n
                if ~visited(k) && MT(j, k) < minW
                    minW = MT(j, k);
                    minJ = k;
                end
            end
        end
    end
    child(minJ) = find(MT(minJ,:) == minW);
    visited(minJ) = true;
end

% 输出每棵子树的根节点和子节点
for i = 1:n
    if child(i) == 0
        fprintf('根节点：%d，子节点：', i);
        for j = 1:n
            if child(j) == i
                fprintf('%d ', j);
            end
        end
        fprintf('\n');
    end
end

完整代码如下：

% 随机生成10个坐标点
n = 10;
points = rand(n, 2);

% 构造邻接矩阵
W = zeros(n);
for i = 1:n
    for j = i+1:n
        W(i, j) = norm(points(i,:) - points(j,:));
        W(j, i) = W(i, j);
    end
end

% Prim算法求解最小生成树MT
MT = zeros(n);
visited = false(n, 1);
visited(1) = true;
for k = 1:n-1
    minW = Inf;
    minI = -1;
    minJ = -1;
    for i = 1:n
        if visited(i)
            for j = 1:n
                if ~visited(j) && W(i, j) < minW
                    minW = W(i, j);
                    minI = i;
                    minJ = j;
                end
            end
        end
    end
    MT(minI, minJ) = minW;
    MT(minJ, minI) = minW;
    visited(minJ) = true;
end

% 将MT分解为n'棵子树
visited = false(n, 1);
visited(1) = true;
child = zeros(n, 1);
for i = 2:n
    minW = Inf;
    minJ = -1;
    for j = 1:n
        if visited(j)
            for k = 1:n
                if ~visited(k) && MT(j, k) < minW
                    minW = MT(j, k);
                    minJ = k;
                end
            end
        end
    end
    child(minJ) = find(MT(minJ,:) == minW);
    visited(minJ) = true;
end

% 输出每棵子树的根节点和子节点
for i = 1:n
    if child(i) == 0
        fprintf('根节点：%d，子节点：', i);
        for j = 1:n
            if child(j) == i
                fprintf('%d ', j);
            end
        end
        fprintf('\n');
    end
end