MATLAB 最小生成树

2744557306

最小生成树

, z4 q3 M% ^0 z' r! G最小生成树(Minimum Spanning Tree, MST) 是一种用于寻找连通图中的最小权重生成树的算法。最小生成树的应用非常广泛，例如在网络规划中，我们需要在一定的成本下，使得网络中的所有节点都能够相互连接，这时候就可以使用最小生成树来解决这个问题。

常用的最小生成树算法有 Prim 算法和 Kruskal 算法，这两种算法都是贪心算法，都是通过不断地选择权重最小的边来构建最小生成树。
& T: d" B0 U7 K2 j! \如何使用 MATLAB 求解最小生成树

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

minspantree 函数的语法如下

1. T = minspantree(G)( e1 q2 B  Y+ j1 N, h3 u- r6 q# P
   

复制代码

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

例

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

1. s = [1 1 1 2 5 3 6 4 7 8 8 8];0 {$ K1 |( T% |4 A$ ^, O
   
2. t = [2 3 4 5 3 6 4 7 2 6 7 5];8 ~+ e6 u- s8 k! c- {) O+ u
   
3. weights = [100 10 10 10 10 20 10 30 50 10 70 10];+ D! `' ~0 E8 E4 A# x
   
4. G = graph(s,t,weights);
   % |- q; C  r$ B+ }5 ]6 f/ T- j4 y3 Y
5. p = plot(G,'EdgeLabel',G.Edges.Weight);. _8 a1 z( i- a- h# g1 L1 ?- ?
   

复制代码

" A$ K8 F* b; n) \3 Y+ a2 Q计算并在图上方绘制图的最小生成树。T 包含的节点与 G 相同，但包含的边仅为后者的子集。
" _: n, t- e3 S* q! w3 }& vT = minspantree(G);
( U8 m+ P8 V0 e, yhighlight(p,T)

% W+ p" z6 m/ b& _4 z  N+ w+ }

; |$ j8 o& {" ?% m4 \