最小生成树matlab源码

以下是使用Matlab实现最小生成树（MST）算法的示例代码：

function [T, W] = mst_prim(A)
% MST_PRIM Minimum Spanning Tree using Prim's algorithm
%   [T, W] = MST_PRIM(A) computes the minimum spanning tree T and its weight
%   W of the graph A using Prim's algorithm.
%
%   Input:
%       A - n-by-n adjacency matrix of the graph.
%
%   Output:
%       T - n-by-n sparse matrix of the minimum spanning tree. T(i,j) = 1 if
%           there is an edge between i and j in the minimum spanning tree,
%           and 0 otherwise.
%       W - the weight of the minimum spanning tree.
%
%   Author: Zhiqiang Wang, zwang@ieee.org
%   Date:   07/01/2018

n = size(A, 1); % number of vertices
T = sparse(n, n); % initialize the minimum spanning tree
W = 0; % initialize the weight of the minimum spanning tree
key = inf(1, n); % the minimum key value of each vertex
pi = zeros(1, n); % the parent vertex of each vertex
visited = false(1, n); % the visited flag of each vertex
key(1) = 0; % start from vertex 1
for i = 1:n
    % find the unvisited vertex with the minimum key value
    u = find(~visited & (key == min(key)), 1);
    visited(u) = true;
    if pi(u) ~= 0
        T(u, pi(u)) = 1; % add the edge to the minimum spanning tree
        T(pi(u), u) = 1;
        W = W + A(u, pi(u)); % update the weight of the minimum spanning tree
    end
    % update the key values of the adjacent vertices
    for v = 1:n
        if A(u, v) ~= 0 && ~visited(v) && A(u, v) < key(v)
            key(v) = A(u, v);
            pi(v) = u;
        end
    end
end

该代码使用Prim算法，输入为一个n-by-n的邻接矩阵A，输出为一个n-by-n的稀疏矩阵T和最小生成树的权重W。其中，稀疏矩阵T中T(i,j)=1表示最小生成树中存在一条从i到j的边，否则T(i,j)=0。