最小生成树prim算法matlb代码

最小生成树（Minimum Spanning Tree, MST）是指在一个加权无向图中，找到一个边的子集，使得这个子集构成的树包含图中所有的顶点，并且边的权值之和最小。普里姆算法（Prim's algorithm）是解决这个问题的一种算法，它通过贪心策略，逐渐增加新的边和顶点，直到构成一棵最小生成树。

以下是使用Prim算法的MATLAB代码示例，该代码演示了如何为给定的图构造最小生成树：

function [MST, cost] = prim(graph)
    % graph: 邻接矩阵表示的图，graph(i, j) 表示顶点i和顶点j之间的边的权重，若无边则为无穷大
    % MST: 最小生成树的边集合
    % cost: 最小生成树的总权值

    [numVertices, ~] = size(graph); % 获取顶点的数量
    visited = false(1, numVertices); % 记录每个顶点是否被访问
    visited(1) = true; % 从顶点1开始构建MST
    edgeCount = 0; % 记录当前MST中边的数量
    MST = []; % 初始化MST边集合为空
    
    while edgeCount < numVertices - 1
        minDist = inf; % 初始化最小距离为无穷大
        u = 0; v = 0;
        
        % 寻找未访问顶点中距离最小的边
        for i = 1:numVertices
            if visited(i)
                for j = 1:numVertices
                    if ~visited(j) && graph(i, j) < minDist
                        minDist = graph(i, j);
                        u = i;
                        v = j;
                    end
                end
            end
        end
        
        % 更新MST和已访问顶点集合
        if u ~= 0 && v ~= 0
            visited(v) = true;
            MST = [MST; u, v, minDist]; % 将找到的边添加到MST集合中
            edgeCount = edgeCount + 1;
        end
    end
    
    % 计算最小生成树的总权值
    cost = sum([MST(:,3)]);
end

使用该函数的示例：

% 定义图的邻接矩阵
graph = [inf, 2, inf, 6, inf;
         2, inf, 3, 8, 5;
         inf, 3, inf, inf, 7;
         6, 8, inf, inf, 9;
         inf, 5, 7, 9, inf];

% 调用prim算法函数
[MST, cost] = prim(graph);

% 输出结果
disp('最小生成树的边和对应的权值：');
disp(MST);
disp(['最小生成树的总权值：', num2str(cost)]);

这段代码会输出最小生成树的边和对应的权值，以及树的总权值。需要注意的是，上述代码示例假设图的输入为一个邻接矩阵，并且图是连通的。对于非连通图，Prim算法将只生成包含所有顶点的连通分量的最小生成树。