MATLAB 最小生成树

2744557306

最小生成树
' Y# E/ E' P/ E! i9 w( d; M# m* K
# I4 b8 E5 S3 e5 h: J最小生成树(Minimum Spanning Tree, MST) 是一种用于寻找连通图中的最小权重生成树的算法。最小生成树的应用非常广泛，例如在网络规划中，我们需要在一定的成本下，使得网络中的所有节点都能够相互连接，这时候就可以使用最小生成树来解决这个问题。
, i/ v; {- A7 y0 E8 S$ k' \
: L  Z: K( Y# i( X9 \常用的最小生成树算法有 Prim 算法和 Kruskal 算法，这两种算法都是贪心算法，都是通过不断地选择权重最小的边来构建最小生成树。
如何使用 MATLAB 求解最小生成树

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

minspantree 函数的语法如下

1. T = minspantree(G)
   # f6 y0 ?9 a& A# V; D1 T\" @

复制代码

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

例

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

1. s = [1 1 1 2 5 3 6 4 7 8 8 8];
   + `$ e% B& q4 X$ C
2. t = [2 3 4 5 3 6 4 7 2 6 7 5];5 }4 v$ E1 J/ g
   
3. weights = [100 10 10 10 10 20 10 30 50 10 70 10];
   9 \' P( f; e% {9 f
4. G = graph(s,t,weights);
   0 V. `: R/ N9 u1 r6 d# A7 h+ N
5. p = plot(G,'EdgeLabel',G.Edges.Weight);
   ! I* b9 R0 H- G  o. w1 I1 p* D4 \

复制代码

* o2 o0 B0 y$ c1 J计算并在图上方绘制图的最小生成树。T 包含的节点与 G 相同，但包含的边仅为后者的子集。
T = minspantree(G);
: F! }& s) @- }8 K! v/ ihighlight(p,T)

. r) o# c2 Z4 R+ o# C" D
1 Q3 W3 c- E5 M, b$ }, D
/ q& d& x9 C% h; |6 R
1 D4 V& D2 Q5 ?$ ~3 ?( c& g6 N0 z