prim算法matlab实现

以下是Prim算法的MATLAB实现代码：

function [mst, total_cost] = prim(graph)
% graph: 邻接矩阵表示的图
% mst: 最小生成树的邻接矩阵表示
% total_cost: 最小生成树的总权值

n = size(graph, 1);  % 节点数目
mst = zeros(n);  % 初始化最小生成树
visited = false(1, n);  % 初始化所有节点未访问
visited(1) = true;  % 从第一个节点开始访问

for i = 1:n-1
    min_edge = inf;
    u = 0;
    v = 0;
    for j = 1:n
        if visited(j)  % 对于已经访问的节点，寻找它的最小边
            for k = 1:n
                if ~visited(k) && graph(j, k) < min_edge
                    min_edge = graph(j, k);
                    u = j;
                    v = k;
                end
            end
        end
    end
    visited(v) = true;  % 将新的节点标记为已访问
    mst(u, v) = min_edge;
    mst(v, u) = min_edge;
end

total_cost = sum(sum(mst));  % 计算最小生成树的总权值

其中，输入参数graph是邻接矩阵表示的图，输出参数mst是最小生成树的邻接矩阵表示，total_cost是最小生成树的总权值。