Matlab最小生成树的邻接矩阵

这里提供一个使用Kruskal算法求解最小生成树的邻接矩阵的Matlab代码示例：

% 假设邻接矩阵为A，n为节点数目
% 初始化父节点数组和秩数组
parent = 1:n;
rank = zeros(1, n);

% 定义边结构体
Edge = struct('u', 0, 'v', 0, 'w', 0);

% 构造边集合
edges = [];
for i = 1:n
    for j = i+1:n
        if A(i, j) > 0
            edge.u = i;
            edge.v = j;
            edge.w = A(i, j);
            edges = [edges, edge];
        end
    end
end

% 按权重从小到大排序
edges = sort(edges, @(e1, e2) e1.w - e2.w);

% 定义最小生成树邻接矩阵
MST = zeros(n);

% Kruskal算法求解最小生成树
for i = 1:length(edges)
    u = edges(i).u;
    v = edges(i).v;
    w = edges(i).w;
    
    % 判断是否在同一集合中
    while parent(u) ~= u
        u = parent(u);
    end
    while parent(v) ~= v
        v = parent(v);
    end
    
    if u ~= v
        % 合并两个集合
        if rank(u) < rank(v)
            parent(u) = v;
        elseif rank(v) < rank(u)
            parent(v) = u;
        else
            parent(v) = u;
            rank(u) = rank(u) + 1;
        end
        
        % 添加边到最小生成树
        MST(edges(i).u, edges(i).v) = w;
        MST(edges(i).v, edges(i).u) = w;
    end
end

这段代码将邻接矩阵A转化为边集合，然后使用Kruskal算法求解最小生成树并构造邻接矩阵MST。需要注意的是，这里假设邻接矩阵是对称的（即无向图），因此MST也是对称的。如果是有向图，那么需要根据Kruskal算法的特性来构造邻接矩阵。