matlab生成最小生成树

最小生成树(Minimum Spanning Tree, MST) 是一种用于寻找连通图中的最小权重生成树的算法。可以使用Matlab中的minspantree()函数来求解最小生成树。首先，需要定义一个边权矩阵，其中每一列表示一条边，从上到下分别为两个顶点以及它们边的权值。然后，使用sortrows函数对边权矩阵的第三列进行排序，得到排序后的边权矩阵。接下来，使用循环遍历每条边，判断当前边连接的两个顶点是否在同一个集合中，如果不在同一个集合中，则将该边加入最小生成树中，并更新顶点集合的标记。最终，得到最小生成树的边集合和总长度。以下是用Matlab代码实现最小生成树的示例：

% 边权矩阵，每一列都表示一条边，从上到下分别为两个顶点以及它们边的权值
b = [1 1 1 2 2 3 3 4; 2 4 5 3 5 4 5 5; 8 1 5 6 7 9 10 3];

% 对边权矩阵按权值进行排序
[B, i = sortrows(b', 3);
B = B';

% 边的条数和点的个数
m = size(b, 2);
n = 5;

% t数组用来标记选中的边，k用来计数，T矩阵用来存储选中的边，c计算最小生成树的总长度
t = 1:n;
k = 0;
T = [];
c = 0;

for i = 1:m
    if t(B(1, i)) ~= t(B(2, i))
        k = k + 1;
        T(k, 1:2) = B(1:2, i);
        c = c + B(3, i);
        tmin = min(t(B(1, i)), t(B(2, i)));
        tmax = max(t(B(1, i)), t(B(2, i)));
        for j = 1:n
            if t(j) == tmax
                t(j) = tmin;
            end
        end
    end
    if k == n - 1
        break;
    end
end

T % 输出最小生成树的边集合
c % 输出最小生成树的总长度

这段代码将输出最小生成树的边集合和总长度。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [MATLAB 最小生成树](https://blog.csdn.net/qq_63585949/article/details/128908785)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *2* [最小生成树matlab求解](https://blog.csdn.net/Planck_meteora/article/details/123342485)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *3* [【MATLAB】最小生成树Kruskal算法](https://blog.csdn.net/weixin_46308081/article/details/119202910)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 33.333333333333336%"]
[ .reference_list ]