MATLAB 最小生成树

2744557306

最小生成树

最小生成树(Minimum Spanning Tree, MST) 是一种用于寻找连通图中的最小权重生成树的算法。最小生成树的应用非常广泛，例如在网络规划中，我们需要在一定的成本下，使得网络中的所有节点都能够相互连接，这时候就可以使用最小生成树来解决这个问题。
' @  k6 M, g( u2 E) [- X& P9 q
0 m6 }) X( U7 y6 p( I常用的最小生成树算法有 Prim 算法和 Kruskal 算法，这两种算法都是贪心算法，都是通过不断地选择权重最小的边来构建最小生成树。
如何使用 MATLAB 求解最小生成树

MATLAB 中提供了 minspantree 函数来求解最小生成树。

minspantree 函数的语法如下

1. T = minspantree(G)4 B. G4 M* ]6 ]+ M8 S4 C& W, j9 Q
   

复制代码

其中，G 是一个图，T 是最小生成树。

例

使用加权边创建并绘制一个立方体图。

1. s = [1 1 1 2 5 3 6 4 7 8 8 8];
   ; J4 m; @  A2 r% _7 F) F6 l* @
2. t = [2 3 4 5 3 6 4 7 2 6 7 5];
   ; t& a0 u\" B# j. M5 b. \. ~9 b5 \0 E
3. weights = [100 10 10 10 10 20 10 30 50 10 70 10];
   % m' g4 F% s2 ~8 U, E! S
4. G = graph(s,t,weights);
   4 S+ s3 ]( s- P1 M\" ?5 L+ c
5. p = plot(G,'EdgeLabel',G.Edges.Weight);4 K9 v6 B1 m4 h8 F5 S  B1 N  H
   

复制代码

计算并在图上方绘制图的最小生成树。T 包含的节点与 G 相同，但包含的边仅为后者的子集。
T = minspantree(G);
highlight(p,T)
6 q& X9 g' _& \" E$ m4 z+ {
& p; e; j' u9 h& q- L
  B1 Q- n9 U7 W* l
# L! \" R; u2 X. r7 b