最小生成树的直径matlab

最小生成树的直径可以通过 Kruskal 算法得到最小生成树，然后利用 DFS 或 BFS 算法遍历该树得到最长路径的长度即为直径。下面是一个基于 Matlab 的实现示例：

function diameter = MST_Diameter(adj_matrix)
% adj_matrix: 邻接矩阵
% diameter: 最小生成树的直径

n = size(adj_matrix, 1);
edges = [];
for i = 1:n-1
    for j = i+1:n
        if adj_matrix(i,j) > 0
            edges = [edges; i,j,adj_matrix(i,j)];
        end
    end
end
edges = sortrows(edges, 3); % 按边权值排序

% Kruskal算法求最小生成树
parent = 1:n;
rank = zeros(n, 1);
mst = [];
for i = 1:size(edges, 1)
    u = edges(i,1);
    v = edges(i,2);
    w = edges(i,3);
    pu = find(parent, u);
    pv = find(parent, v);
    if pu ~= pv
        mst = [mst; u,v,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

% DFS遍历最小生成树
visited = zeros(n, 1);
stack = [1, 0]; % 栈中存储节点和对应的深度
depth = 0;
while ~isempty(stack)
    node = stack(end, 1);
    depth = stack(end, 2);
    stack(end, :) = [];
    visited(node) = 1;
    for i = 1:size(mst, 1)
        if mst(i,1) == node && ~visited(mst(i,2))
            stack = [stack; mst(i,2), depth+1];
        elseif mst(i,2) == node && ~visited(mst(i,1))
            stack = [stack; mst(i,1), depth+1];
        end
    end
end
diameter = depth;

该实现首先将邻接矩阵中的边按权值排序，然后通过 Kruskal 算法得到最小生成树。接着利用 DFS 遍历该最小生成树，从根节点开始计算深度，最终得到最长路径的长度，即为最小生成树的直径。