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

2744557306

Kruskal算法是一种贪心算法，用于找到连接的加权图的最小生成树。它找到了一组边，形成了一个包含每个顶点的树，树中所有边的总权重被最小化。
以下是Kruskal算法的简要概述：

; N- f0 d& o, `5 U$ w1.排序边: 将所有边按照权重的非递减顺序排序。
5 R! g) I6 K# N/ r5 P2.初始化: 创建一个森林（一组树），其中每个顶点都是一个单独的树。
3.遍历边: 遍历所有边，从最小权重到最大权重。
' y; i+ @8 x) ^  _4 K3 E) Y4.检查环路: 对于每条边，如果将其包含在生成树中不会导致环路，则将其添加到生成树中。否则，丢弃它。
7 c$ a+ p" ?9 E7 F5.合并: 如果将边添加到生成树中，则执行合并操作，将两棵树合并为一棵树。
$ X; ?( t) N5 A$ P* J" ~, d4 D
) W$ m6 e7 S3 A: ]) g5 r" _以下是Kruskal算法的Python实现：

1. class Graph:
   4 G  X8 A3 @/ a6 s8 h4 }8 [
2. : T, t) r3 H: \) ?3 Q; h3 ^/ u, `
   
3.     def __init__(self, vertices):
     s7 L3 a0 G. o; }7 q
4. $ n/ ]# n# f% t- F
   
5.         self.V = vertices
   % z! w! |- t- H4 b, g' q; ~
6. 
   . c5 f- Z3 v3 ^# T7 o
7.         self.graph = []
   : g9 _1 k, N\" Z% e1 J
8. 3 g) p0 k6 {\" Q1 @) m3 ?
   
9. 
     m2 E8 d$ [; \
10. 
    6 l) m0 c) h4 I/ x: J5 Y/ d6 D# O$ V
11.     def add_edge(self, u, v, w):  l9 O3 M+ c2 b# s
    
12. 
    4 Q% T* ~* ?5 k# q7 ]
13.         self.graph.append([u, v, w])' J) X8 g2 c8 g- M- E8 j
    
14. $ N7 Q# {/ J) e+ f
    
15. 
    & B1 x! H& ?. x
16. 7 l# A' @9 ?! _- Z# z/ `
    
17.     def find(self, parent, i):
    / h7 e1 R8 a. Q! x* o6 K
18. 
    ( y+ F3 w8 N\" l
19.         if parent[i] == i:, t0 s9 `; ?! M2 h, M0 p- q
    
20. 
    8 ^* N+ F; G3 n  `1 i( z
21.             return i
    ) w+ \) K: S0 ^5 Y4 Z
22. : |3 I  @- d/ K; K6 p
    
23.         return self.find(parent, parent[i])
    / P. c6 g\" ?; `/ F/ L6 s0 R
24. 3 |  \' H( M$ M\" d1 ~' P$ h
    
25. 4 h9 a3 _1 r& C# D) P
    
26. 0 I$ R6 h8 F2 g& a' X( Z
    
27.     def union(self, parent, rank, x, y):
    # F3 I2 |* i8 Y2 Q  J6 p
28. 0 z0 Q) u! E) P) o1 y% N& f5 u
    
29.         x_root = self.find(parent, x)
    5 L+ T- Q, I* ?0 ?
30. 
    - K% Q6 L1 b6 E9 d/ X# C
31.         y_root = self.find(parent, y)
    2 Z' _* V$ L) ?2 J
32. 
    7 u+ a+ a0 E  ?: v6 q9 }& U
33. 
    % o7 H) r; j* v+ G4 M
34. 
    , e( }: ]7 G: o3 Q5 U4 y9 R
35.         if rank[x_root] < rank[y_root]:  k& D+ J5 `% [' C; ]; r5 |
    
36. 
    7 y3 R4 C2 d. s: k/ d, Y0 f. Z
37.             parent[x_root] = y_root6 I, ?$ l8 ], O4 z4 D! e; V+ g
    
38.   c4 W\" U1 T5 {) @- E8 g6 ~
    
39.         elif rank[x_root] > rank[y_root]:6 U1 g' X+ L6 F5 w. F* s) P+ G  d. ~
    
40. ' c/ W' N# H3 s( b0 ~! L# ?+ T
    
41.             parent[y_root] = x_root4 |) G* ~# G2 D
    
42. 1 q2 o# J4 M) y$ y
    
43.         else:
      t6 g7 _) C6 S
44. 
    $ F( j+ g7 _9 n; g( |
45.             parent[y_root] = x_root
    * ~9 q1 _9 `\" K, S\" B! }
46. 3 l' B% w- b' V( u7 I! g& I6 y
    
47.             rank[x_root] += 1
      {: B) D3 H; L' I/ R5 c2 T) O
48. 
    2 i, H5 I$ w( M! @  R
49. 
    . S  a9 y. g* Z# @: |\" l' y( A
50. 6 S8 ^% @0 {. b- R+ k% y
    
51.     def kruskal_minimum_spanning_tree(self):
    + k3 Y\" `4 s6 ]2 Q2 n+ {. L
52. & f$ Y% C: U2 B; g\" X- H0 i
    
53.         result = []0 E$ q& j- p3 R. {
    
54. 0 l. w# S( L, ?  M
    
55.         i, e = 0, 0, D; I2 X: I2 u
    
56. 
    3 A4 h( m+ K& `- G\" J
57. 5 p/ ~. E* l; \# I
    
58. - |0 E* v9 c$ U
    
59.         self.graph = sorted(self.graph, key=lambda item: item[2])
    9 S* F0 E. B. K2 i- X* J3 G
60. 
    . x# m9 V' ]/ i. f8 Q
61.         parent = []1 b' _+ V3 ]- C5 ^2 o8 a: C
    
62. : Q6 x; p  z3 i* U
    
63.         rank = []
    4 g\" p$ L) S: k# B& D( k+ q
64. ( ?9 ]( L( a% E$ r( C
    
65. 
    $ u# h/ ]; t* y& h; A7 @
66. + k( E  O- v! G: k\" P3 F
    
67.         for node in range(self.V):
    ' U' h1 K4 {9 H% a! D  r
68. ) \6 U3 W2 h6 g9 ]: t9 n
    
69.             parent.append(node)+ P\" T, {/ ~- ~- g) V% P) ^+ K
    
70. 
    1 q; m% z4 L& A
71.             rank.append(0)' ~  d8 }5 }: {0 f4 |- ]3 G
    
72. 7 }) C# ]\" Y/ M/ \! K& _
    
73. 
    % `6 ]: i( N: H3 ~0 Q$ o, L9 c, v/ g
74. 3 X, g# }6 q/ D& c
    
75.         while e < self.V - 1:( D& |$ s: p4 t  c( ^
    
76. ) O: I  e- _! X8 N1 U
    
77.             u, v, w = self.graph[i]& c  Z! T* m8 t$ q8 P; g( W
    
78. 
    # _\" u5 y\" B\" v/ Q1 h' U* C
79.             i += 1
    . e1 o  c& \' ^/ E7 i  ?0 Q5 c
80. 
    % f. K: q' l+ y
81.             x = self.find(parent, u)9 t- @9 x/ F8 A, t  V
    
82. 
    ; e* I* j\" [4 _  V
83.             y = self.find(parent, v)
    $ |4 E7 R( {( |/ t6 d7 x& [( ]  n  H/ r
84. 
    0 ?* w/ N9 [/ Y. ^! E7 M7 m\" ^
85. ' d3 S* B* }# B8 s1 O/ m( p) k
    
86. 
    , f2 y: j# g$ ~$ |2 |8 A\" d
87.             if x != y:
    5 m\" z\" _\" F7 d1 z: ^& w1 @7 V8 K
88. 
    / T  @) C! s! Z1 o! z
89.                 e += 19 s- k& j6 \6 `2 t& j# r
    
90. 
    . [6 j2 H, V  m$ N1 |
91.                 result.append([u, v, w])
    8 T6 d; q4 T  n* Y\" r, e. R! H
92. 
      A. n1 K/ @0 o( \
93.                 self.union(parent, rank, x, y)
    ( k- y# M\" d! `, G% \
94. 
    4 e/ {0 u' }\" N6 F+ ]
95. : q- o& V. e* P( O& a& Y5 l7 B9 ~1 b
    
96. 
    . c! J  M# }\" U% ?  k+ s! R8 R: Z
97.         return result
    & n3 g4 v8 z+ u3 [; [5 p
98. 
    # R4 f0 d7 F- T- b+ P
99. 3 L# a0 c8 L2 ]6 }2 N1 |
    
100. ) \$ y% h. B3 H/ z
     
101. g = Graph(4)) c( k- A6 d. G, U- g, W; k
     
102. ) U2 e. j- ], }\" F
     
103. g.add_edge(0, 1, 10)8 t& N2 K% V3 l, V* T! m0 ]+ ?& {
     
104. 
     ' b8 H% [4 V) C& `
105. g.add_edge(0, 2, 6)* k+ N' N3 x1 ^, C2 h
     
106. & u& e4 j5 p- [+ L
     
107. g.add_edge(0, 3, 5)
     6 m+ C& z. e4 i  m) H\" ]
108. 
     $ E5 V$ n) e0 C. ^* t4 C\" t% n/ P
109. g.add_edge(1, 3, 15)
     * z. |% U, O0 I. A. W. n
110. 2 _% p- W* A: x6 u
     
111. g.add_edge(2, 3, 4). L' [  g' N+ ]; j7 I7 b
     
112. 1 c# B& _# I& r\" _0 |7 v4 r
     
113. 
     0 a) p  ]( U5 r\" u- M$ L
114. 7 f; x' z* D4 W1 c% L5 {
     
115. print("最小生成树的边:")/ c5 z6 @# D+ }0 {* G$ l& G. D
     
116. 
     1 b& S5 A+ S, `7 O$ l4 z: G
117. print(g.kruskal_minimum_spanning_tree())

复制代码

这段代码定义了一个Graph类，其中包含添加边的方法、查找节点的父节点的方法、执行并操作的方法以及使用Kruskal算法查找最小生成树的方法。
6 a/ e2 D. Y9 X( f5 e* j+ v+ q
/ u4 C& ~$ u# _) x% V$ N7 b9 {