prim算法求最小生成树 matlab

好的，以下是使用Prim算法求最小生成树的Matlab代码：

function [MST, total_weight] = prim(adj_matrix)
% adj_matrix: 邻接矩阵，表示图的连接情况和边权值
% MST: 最小生成树的邻接矩阵
% total_weight: 最小生成树的总权值

n = size(adj_matrix, 1); % 图中节点数
visited = false(1, n); % 标记节点是否已经被访问
key = inf(1, n); % 存储每个节点到最小生成树的距离
parent = zeros(1, n); % 存储每个节点在最小生成树中的父节点

% 从第一个节点开始构建最小生成树
key(1) = 0;
parent(1) = -1;

for i = 1:n-1
    % 找到距离最小生成树最近的节点
    min_key = inf;
    min_index = -1;
    for j = 1:n
        if ~visited(j) && key(j) < min_key
            min_key = key(j);
            min_index = j;
        end
    end
    
    visited(min_index) = true;
    
    % 更新与该节点相邻的节点到最小生成树的距离和父节点
    for j = 1:n
        if ~visited(j) && adj_matrix(min_index, j) < key(j)
            key(j) = adj_matrix(min_index, j);
            parent(j) = min_index;
        end
    end
end

% 构建最小生成树的邻接矩阵
MST = zeros(n);
for i = 2:n
    MST(i, parent(i)) = adj_matrix(i, parent(i));
    MST(parent(i), i) = adj_matrix(i, parent(i));
end

total_weight = sum(MST(:))/2; % 计算最小生成树的总权值

end