Kruskal算法生成最小生成树 实例

2744557306

Kruskal算法是一种贪心算法，用于找到连接的加权图的最小生成树。它找到了一组边，形成了一个包含每个顶点的树，树中所有边的总权重被最小化。
2 R. L- L* m* U以下是Kruskal算法的简要概述：
6 F0 G% M6 S% ~) }$ E( \1 d) ^
; I# b- W1 ~5 O, @1.排序边: 将所有边按照权重的非递减顺序排序。
2.初始化: 创建一个森林（一组树），其中每个顶点都是一个单独的树。
  U4 d8 H* i8 J2 F3 d  {4 X3.遍历边: 遍历所有边，从最小权重到最大权重。
2 P8 W$ i$ M/ C7 s4 o( _: S4.检查环路: 对于每条边，如果将其包含在生成树中不会导致环路，则将其添加到生成树中。否则，丢弃它。
0 H$ a- t7 u/ X, V9 y* Q* j. d8 J) u3 R5.合并: 如果将边添加到生成树中，则执行合并操作，将两棵树合并为一棵树。

6 I( P4 H% C& w+ h+ Z, p以下是Kruskal算法的Python实现：

1. class Graph:) N* Z2 \3 M% S: e4 f. C- z3 u
   
2. + R% X; d! t' p1 E* h3 R7 u
   
3.     def __init__(self, vertices):
   2 P/ ^. l; N9 C( ?
4. 
   $ N% i) b5 U6 B\" r, X9 F, F
5.         self.V = vertices: C+ `4 z2 X! ~  T; P2 R
   
6. 9 ?0 {/ u. F3 l8 n/ j; H
   
7.         self.graph = []
   4 b5 b) u; ?  `; T* v( E
8.   }  U, @, {6 P$ I  ]( d. R, D2 n
   
9. 
   . V\" i) D, N0 j: U
10. 
    0 z* [2 ?$ ]  C9 A5 I
11.     def add_edge(self, u, v, w):3 ~' U4 t) Y! R* `\" |2 s9 O
    
12. 
    , i- {$ N5 [+ K2 y: N' ]9 h
13.         self.graph.append([u, v, w])/ B  [' Q. g5 V7 J
    
14. 
    4 ]1 N& \& s# @9 g6 C1 _
15. 
    1 e8 ]  r  \2 i8 ?: _4 r
16. - C* ]* _8 g/ h0 n
    
17.     def find(self, parent, i):! e; m+ G/ H: T( J4 A
    
18. 
    * |2 P* }4 J  n$ _8 m6 @* u' e
19.         if parent[i] == i:0 P4 ~+ i\" V$ e3 C( H$ |
    
20. 
    8 d) T; Z4 P  D1 h( ~
21.             return i9 @6 @& C) Z  k
    
22. + p. w' X/ s\" Q) s& G* p
    
23.         return self.find(parent, parent[i])
    3 `- T6 m/ A3 W5 w
24. 
    ! _5 L+ t9 @3 u
25. \" A) a7 w8 x; ?1 n5 n9 D
    
26. - g( n0 B7 L: F  ~. G
    
27.     def union(self, parent, rank, x, y):
    : e+ f. c2 M$ y1 ~. G$ q
28. 
    + L/ O; E* ^- f& I& ?. ]
29.         x_root = self.find(parent, x)
    4 _# q: Y5 e\" X3 E  E
30. 
    8 `- J5 R) N$ k
31.         y_root = self.find(parent, y)2 z( r/ K; k' Z
    
32. ) q& J/ M+ v7 O! I! h9 x/ E0 Y
    
33. 
    7 ?$ Q: f  J3 ^8 U! L
34. 8 s7 F0 ]5 B; v\" Z. F: l
    
35.         if rank[x_root] < rank[y_root]:& h8 \' ], \5 {3 E
    
36. ; _( [, E  i# T\" M: X# I
    
37.             parent[x_root] = y_root
    + z0 k\" L7 Y- H/ _\" A
38. , [6 ^) J5 r+ j' z2 |. R
    
39.         elif rank[x_root] > rank[y_root]:
    * i: @5 ?( Z* n
40. 4 B; G. g# O* ?7 ^7 f) g! d7 @+ H
    
41.             parent[y_root] = x_root. O7 u! n  X! J2 r
    
42. 3 f- A: o- {2 ?7 h/ y
    
43.         else:1 G, k8 O8 ^4 W! q2 j
    
44.   }0 h# l  ^, O, ?
    
45.             parent[y_root] = x_root
    / D; D0 K0 [! M* @- L\" t
46. ! s  S  ~4 C) z: ^5 T% ]' X  g3 Z4 e
    
47.             rank[x_root] += 1
    ! D; i4 p8 |$ p5 m( h& I
48. 
    ; i3 b2 u3 k9 S3 j4 T; m+ F% D
49. 
    # ]% [3 G2 n# I& g# u( I+ D3 J8 f
50. 
    0 e% D* I6 F. j7 t; m\" Y\" o
51.     def kruskal_minimum_spanning_tree(self):
    1 N; A\" l. A3 R+ e4 U+ V9 e
52. 
    5 O3 `6 B$ o4 o. z2 t3 U
53.         result = []9 W, e. ^\" x0 C\" {6 N0 q$ @
    
54. 
    3 T8 U9 t- z% p5 A( l
55.         i, e = 0, 0* K3 \4 v! ~0 a. G
    
56. 
    7 S6 e! z+ p; r+ [% r
57. % }. Y\" J* g( x5 K\" Z* }
    
58. 
    ' L4 J' k8 z. d8 ?7 A
59.         self.graph = sorted(self.graph, key=lambda item: item[2])
      |, r% ]) O, _/ D* p
60. 
    ! Y) N3 @2 C2 d6 R, B: }
61.         parent = []4 e. o' u3 I. |& \* |6 a5 T
    
62. 
    2 {# r& S3 [$ W0 [
63.         rank = []
    + P+ n# F1 x% [! O1 A1 B
64. 4 v# E. d3 Y6 g
    
65. 
    9 z! P/ K. p5 l5 W# t\" b
66. 
    3 ~& t9 E, o8 z, ?
67.         for node in range(self.V):
    6 W& j8 D  B' P$ f$ y\" q* r
68. * {; |4 Q: `! H# o\" x\" f\" @
    
69.             parent.append(node)8 Q# g, v- F$ c; t8 m* `
    
70. ) D\" h% Z' x  V0 ^/ p. n
    
71.             rank.append(0)
    0 L4 r  r0 W* z) O/ q' y
72. 5 }* x* ?' s. T( n1 p
    
73. 5 D4 M- {  v' i, {7 e( c2 u. q% M
    
74.   G8 \! Y1 {/ ^' R7 n! C& E% T
    
75.         while e < self.V - 1:8 r7 [3 f! k\" |( Z, P
    
76. 
    5 v0 e7 E0 B1 C1 k
77.             u, v, w = self.graph[i]
    / j8 W% U  P6 g4 k; }, F
78. 
    $ T\" n\" F  h$ x: a
79.             i += 1
    4 R5 w* v8 F7 {/ o: U\" }
80. 6 |# E6 f, P/ {$ p+ \
    
81.             x = self.find(parent, u)$ Z! ?\" Z; q9 Z# y) f
    
82. 7 X* _, s- b# V
    
83.             y = self.find(parent, v)
    ; t; [! C* G% Q. u5 h7 F
84. 
    0 o! \, b' j3 C/ E
85. 5 H+ }6 r8 n' D) a4 l
    
86. - m( u4 n7 q2 {& }
    
87.             if x != y:
    - J4 [5 l* E6 B) V4 a$ C
88. ' B  C6 E7 n7 i
    
89.                 e += 1
    ( H% X: u- J2 @4 t- Y
90. : w1 s# j2 J6 Y) g
    
91.                 result.append([u, v, w])! a5 c( r\" q0 _. s3 F
    
92. ' Q* a4 q( k  E4 @+ \
    
93.                 self.union(parent, rank, x, y)
    5 e' \& z8 W. W0 O: A
94. \" m4 @: N8 x4 F' }( K9 g
    
95. 
    6 M7 d& N- i; _+ D5 s8 `
96. . ?( u5 K; @! b
    
97.         return result9 F\" }' @4 e1 c
    
98. / k  `9 [9 k\" C\" C: v* S( X; @
    
99. 
    : u* ]  g  a! m- V- K$ _
100. 9 V/ `; x0 s3 R) B. @\" e9 h\" d
     
101. g = Graph(4)3 E3 V  n\" x8 z% I
     
102. 
     , T7 h8 m4 l& E  @& ^7 @5 R0 K$ J% p5 {
103. g.add_edge(0, 1, 10). s: g, S# E& C/ g, Q
     
104. 
     9 q2 e9 d: W+ r3 P
105. g.add_edge(0, 2, 6)
       Q7 I0 u* X6 V' M# {
106.   s8 A% f! k) q8 A& H0 w8 {
     
107. g.add_edge(0, 3, 5)
     ' ]: u( \% a; u+ F6 f, ]0 H: K( U6 Z
108. % \5 i3 X+ `: K; ]2 y( T
     
109. g.add_edge(1, 3, 15)
     ) J# L+ H3 N# ^' K4 Z( t
110. 2 W; x4 Y6 P0 ~9 }+ z' G\" i% @
     
111. g.add_edge(2, 3, 4)8 A! ~; E9 Q\" P$ @
     
112. . O, U+ R( q3 Y
     
113. 
       L8 ^$ o* z5 W/ O
114. ( g5 c( @$ `  Q\" G
     
115. print("最小生成树的边:")# L8 c9 Z- _4 B, z; e& e9 R1 q4 Q
     
116. 1 y' F0 S) `7 P: F8 i9 g
     
117. print(g.kruskal_minimum_spanning_tree())

复制代码

这段代码定义了一个Graph类，其中包含添加边的方法、查找节点的父节点的方法、执行并操作的方法以及使用Kruskal算法查找最小生成树的方法。

4 @: q8 |2 V" r4 Q& p( P! F* O
1 [( P$ T: J1 _4 F1 k" U3 x5 t