用赋权图的边权矩阵求其最小生成树的kruskal算法的matlab代码

Kruskal算法是求无向图最小生成树的一种贪心算法，其核心思想是通过选择边集合中边权最小的边并且不构成环，直到生成树的边数达到n-1条为止。赋权图的边权矩阵可表示为一个n*n的矩阵，其中aij表示节点i到节点j的边权。

下面是基于赋权图的边权矩阵求最小生成树的kruskal算法的matlab代码：

function mst = kruskal_adjmat(w)
% 输入：赋权图的边权矩阵w，w(i,j)表示i到j的边权。
% 输出：最小生成树的边集mst，每条边为起始点、终止点和边权组成的三元组。
n = size(w, 1); % 赋权图的节点个数
E = zeros(n * (n-1) / 2, 3); % 边集合，每条边为起始点、终止点和边权组成的三元组。
idx = 0;
for i = 1:n
for j = i+1:n
if w(i,j) ~= 0 % 若i到j存在边，则加入边集合。
idx = idx + 1;
E(idx,:) = [i,j,w(i,j)];
end
end
end
E(idx+1:end,:) = []; % 去除边集合中的冗余元素。
E = sortrows(E, 3); % 根据边权排序。
mst = zeros(n-1, 3); % 最小生成树的边集合。
u = 1:n; % 节点所属连通分量的标记。
k = 0; % 最小生成树中已选择的边数。
for i = 1:size(E,1)
if k == n-1 % 边数已达到n-1，退出循环。
break;
end
s = E(i,1); % 当前边的起始点。
t = E(i,2); % 当前边的终止点。
if u(s) ~= u(t) % 如果起始点和终止点所属的连通分量不相同，则选择该边。
k = k + 1;
mst(k,:) = E(i,:);
% 将起始点和终止点所属的连通分量合并。
temp = u(s);
u(u == temp) = u(t);
end
end

说明：该算法首先将边集合中的边按边权从小到大排序，然后依次选择边集合中的边，如果该边的起始点和终止点不在同一个连通分量中，则选择该边，将起始点和终止点所属的连通分量合并，并将该边加入最小生成树的边集合。最终算法输出由n-1条边组成的最小生成树。