prim算法matlab

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

function [MST, total_weight] = prim_algorithm(W)
% PRIM_ALGORITHM Prim's minimum spanning tree algorithm.
%   [MST, total_weight] = PRIM_ALGORITHM(W) finds the minimum spanning tree 
%   of an undirected graph represented by the weight matrix W, where MST is 
%   the adjacency matrix of the minimum spanning tree and total_weight is 
%   the total weight of the minimum spanning tree.
%
%   Example:
%
%       W = [0, 2, 0, 6, 0;
%            2, 0, 3, 8, 5;
%            0, 3, 0, 0, 7;
%            6, 8, 0, 0, 9;
%            0, 5, 7, 9, 0];
%       
%       [MST, total_weight] = prim_algorithm(W)

n = size(W, 1); % number of vertices

% Initialize the set of vertices included in the minimum spanning tree
included = false(1, n);
included(1) = true;

% Initialize the minimum distances from the included vertices to the
% remaining vertices
min_dist = W(1, :);

% Initialize the adjacency matrix of the minimum spanning tree
MST = zeros(n);

% Loop over n-1 edges to add to the minimum spanning tree
for i = 1:n-1
    % Find the vertex with the minimum distance to the included vertices
    [~, j] = min(min_dist(~included));
    
    % Add the minimum distance edge to the minimum spanning tree
    MST(j, find(included)) = W(j, find(included));
    MST(find(included), j) = W(find(included), j);
    
    % Update the set of included vertices and the minimum distances
    included(j) = true;
    min_dist = min(min_dist, W(j, :));
end

% Calculate the total weight of the minimum spanning tree
total_weight = sum(MST(:))/2;

其中，输入参数`W`是一个$n\times n$的权重矩阵，表示无向图的权重。输出参数`MST`是一个$n\times n$的矩阵，表示最小生成树的邻接矩阵；`total_weight`是最小生成树的总权重。