matlab最小生成树算法Prim

Prim算法是一种经典的最小生成树算法，它的基本思想是从一个顶点开始，每次将离该点最近的未加入树中的顶点加入树中，直至所有的顶点都被加入树中。下面是MATLAB实现Prim算法的代码：

function [T, cost] = prim(A)
% A: n x n的邻接矩阵，表示无向带权图
% T: 最小生成树的邻接矩阵
% cost: 最小生成树的权值之和

n = size(A, 1);
T = zeros(n); % 最小生成树的邻接矩阵
visited = zeros(1, n); % 标记顶点是否已被访问
visited(1) = 1; % 从顶点1开始

for k = 1:n-1 % 找n-1条边
    mincost = inf;
    for i = 1:n % 遍历所有已访问的顶点
        if visited(i) == 1 % 如果顶点i已被访问
            for j = 1:n % 遍历所有未访问的顶点
                if visited(j) == 0 && A(i,j) < mincost
                    % 找到距离已访问的顶点最近的未访问的顶点
                    mincost = A(i,j);
                    p = i; % 记录该边的起点
                    q = j; % 记录该边的终点
                end
            end
        end
    end
    T(p,q) = mincost; % 将该边加入最小生成树
    T(q,p) = mincost;
    visited(q) = 1; % 标记顶点q已被访问
end

cost = sum(sum(T)); % 计算最小生成树的权值之和

该算法的时间复杂度为O(n^2)，因此适用于较小规模的图。