【图论】【Matlab】最小生成树之Kruskal算法【贪心思想超详细详解Kruskal算法并应用】

2744557306

实际问题引入
# {' W& S/ F5 g( ]
实这道题的答案，其实就是找到这个图的最小生成树。
. {& k. D4 A* s( ~( V7 m
0 a+ F2 ~- w5 G8 o9 \Kruskal算法
; L; x: u( _- b( I; f* E  c此算法可以称为“加边法”，初始最小生成树的边数为 0，每迭代一次就选择一条满足条件的最小代价的边，加入到最小生成树边的集合里面。
其实核心思想就是贪心思想：通过局部最优达到整体最优
+ A) b, X1 v& t7 k. Y
将所有的边权进行排序
不断迭代选择权最小的边，直到所有的点被连起来（边数=节点数-1）。
在迭代期间，如果边构成了环，就要丢弃该边，因为树中是不存在环的！
整体代码展示
4 H- m  Q. g4 k$ [6 D6 p在matlab中，最小生成树的生成直接用minspantree()函数就行。

1. s=[1,1,1,1,2,2,3,3,4,4,5,5,6];0 D  @7 J  B! u# k; W5 @
   
2. t=[2,3,4,5,3,6,5,7,5,6,6,7,7];8 u* l/ h1 k8 e% A+ I! g9 _8 u
   
3. w=[35,24,10,25,25,20,15,11,12,30,15,25,18];
   8 O8 Y# N( Q2 g4 A3 M  m5 @
4. names={'1','2','3','4','5','6','7'};\" ]: ]* r- B' Q9 t0 q) G
   
5. G=graph(s,t,w,names);6 U+ F: K1 v/ K& f3 x+ ~- T
   
6. p=plot(G,"EdgeLabel",G.Edges.Weight);
   4 ^8 q* I5 k$ A) n) }& C
7. % 求解最小生成树7 i( `2 `  E/ F
   
8. T=minspantree(G,"Method","sparse");. g3 A0 n. B  |7 [; z5 W  {
   
9. % sparse代表的是Kruskal算法4 |' i8 C$ Y( o
   
10. % dense代表的是Prim算法
      \  q- ?; a1 N
11. 
    0 a! \! ?8 a* S2 C1 z
12. % sparse:Kruskal算法( C' ^) U; |! f$ t\" g3 B8 p  x9 x
    
13. % 算法按权重对所有的边排序，然后将不构成循环的边添加到树中
    ) @  K; k, ]; P5 i: a\" p
14. p=plot(G,"EdgeLabel",G.Edges.Weight);\" n0 D, Q- n0 s/ o( V8 K- X
    
15. highlight(p,T,"NodeColor","red","EdgeColor","red"); 4 `3 e& I( F* T\" O0 J% i
    
16. % 将最小生成树的边设置为红色!
    ' l0 G' d% \  m

复制代码

6 t, R) Y% _$ f
( c9 N3 g: r- a& e. B生成的最小生成树：

我们也可以把最小生成树的边和节点打印出来，也可以把整段路的权加起来看看：
尾声

看到这里，相信我们已经学会Kruskal算法寻找最小生成树的过程了，当然，这离数学建模的要求，离我们的目标还非常遥远，博主在不断学习的过程中，也希望可以通过分享学习日记的方式带动大家！

% U, f% R- G' W0 |0 H
/ @' T' W% n$ h