matlab最小生成树

Kruskal算法是一种用于求解最小生成树的算法，它的基本思想是将所有边按照权值从小到大排序，然后依次加入到生成树中，如果加入一条边会形成环，则不加入该边。最终得到的生成树就是最小生成树。

在MATLAB中实现Kruskal算法，可以先将所有边按照权值从小到大排序，然后依次加入到生成树中，使用并查集来判断是否形成环。具体实现可以参考以下步骤：

1. 将所有边按照权值从小到大排序。

2. 初始化并查集，将每个节点都单独成为一个集合。

3. 依次加入边，如果加入一条边会形成环，则不加入该边。

4. 最终得到的生成树就是最小生成树。

具体实现可以参考以下MATLAB代码：

function [MST, cost] = kruskal(G)
% G为邻接矩阵，表示图的边权
n = size(G, 1);
E = [];
for i = 1:n
for j = i+1:n
if G(i,j) >
E = [E; i, j, G(i,j)];
end
end
end
E = sortrows(E, 3); % 按照边权从小到大排序
parent = 1:n;
rank = zeros(1, n);
MST = [];
cost = ;
for i = 1:size(E,1)
u = E(i,1);
v = E(i,2);
w = E(i,3);
pu = find(parent, u);
pv = find(parent, v);
if pu ~= pv % 如果不在同一个集合中，则加入该边
MST = [MST; u, v];
cost = cost + w;
if rank(pu) < rank(pv)
parent(pu) = pv;
elseif rank(pu) > rank(pv)
parent(pv) = pu;
else
parent(pv) = pu;
rank(pu) = rank(pu) + 1;
end
end
end

end

其中，find(parent, u)和find(parent, v)是并查集中的查找操作，用于查找节点u和节点v所在的集合。如果它们在同一个集合中，则说明加入该边会形成环，不加入该边；否则，将它们所在的集合合并成一个集合，并将该边加入到生成树中。rank数组用于记录每个集合的深度，用于优化并查集的合并操作。