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

2744557306

Kruskal算法是一种贪心算法，用于找到连接的加权图的最小生成树。它找到了一组边，形成了一个包含每个顶点的树，树中所有边的总权重被最小化。
以下是Kruskal算法的简要概述：
( ?  N7 }1 r! x3 o( d: I& d
1.排序边: 将所有边按照权重的非递减顺序排序。
5 z5 U$ a6 @* X3 i- Y7 S2.初始化: 创建一个森林（一组树），其中每个顶点都是一个单独的树。
' t1 O* d  x7 l4 Y/ u3.遍历边: 遍历所有边，从最小权重到最大权重。
- g9 Y  g% o% ?# b# p0 k4.检查环路: 对于每条边，如果将其包含在生成树中不会导致环路，则将其添加到生成树中。否则，丢弃它。
  ?  r: f/ s7 X: @* H" B& q2 f! M1 @5.合并: 如果将边添加到生成树中，则执行合并操作，将两棵树合并为一棵树。
3 c7 F2 S! c5 P9 C2 d8 \. c3 g# m
+ A; l3 H  y9 W以下是Kruskal算法的Python实现：

1. class Graph:' t- b+ X2 j8 f4 |) r% L
   
2. 2 `1 w( z# V\" J: x4 O
   
3.     def __init__(self, vertices):
   * D- e- S) I. q7 E; v$ B! u
4. 
   ' j+ P5 i' X\" F: l( I0 ?* l; Z0 t# }0 A
5.         self.V = vertices
   & d1 {) n0 [- p: f: F( U3 j' Q
6. 
   2 ?7 d$ M% G! S8 s
7.         self.graph = []  I! n& \\" t/ U* C) z  {3 k
   
8. 8 a- n  I- z  o' U/ [/ S
   
9. : }( N( M, W- X2 a% z5 ~5 ~
   
10. 
    ! i) ~: P. B# f* Y  }! s3 H
11.     def add_edge(self, u, v, w):
    ' c: ?) a- Y! y' E: L7 G
12. 
    $ w\" e& c8 S% y! F7 b8 ^
13.         self.graph.append([u, v, w])
    # i  K2 M* @5 W' ?6 a0 e
14. 4 B1 d, Y: s# v) l# b
    
15. 
    9 Z5 ~8 B' l, g7 L# G
16. 2 G) C9 B, O; [
    
17.     def find(self, parent, i):
    ; H9 p\" n  D% `( Y
18. 3 b9 Q, x9 a- x1 v
    
19.         if parent[i] == i:4 q. Q0 c+ a& W# J$ [' [
    
20. 
    , v, i+ M6 k# u7 m, k# t% W- J, e
21.             return i3 b) d9 i5 i/ m: @/ O
    
22. ' K1 D' T5 C' S
    
23.         return self.find(parent, parent[i])9 L4 t1 \. f, p& p% E
    
24. 7 U$ d: z3 M6 m
    
25. 
    ' K' L$ T1 c: Y0 i; K
26. 3 o3 F8 J+ U8 A9 S
    
27.     def union(self, parent, rank, x, y):
    / S' B* s( D& g4 L7 b2 u
28. 
    * Z! E/ Q- [  f/ R' v7 a
29.         x_root = self.find(parent, x)
    7 E+ O5 r7 w, k/ @' w: S1 I0 B* y
30. 0 i  d: b; h) b7 Y$ z
    
31.         y_root = self.find(parent, y)7 O\" ~8 V3 C4 z- Q1 J
    
32. 
    : d7 `4 O( j$ {. O4 d1 D- c
33. 
    ) \/ a) v& \, k& B! ~, b) y
34. 
    % k# x! `! d( t6 E6 r
35.         if rank[x_root] < rank[y_root]:
    7 P/ s( `# @\" h: }9 a1 I6 @$ @* M
36. 
    & N. ~- R' y$ r* K
37.             parent[x_root] = y_root+ z2 x; G& d, u& x' Y/ m
    
38. 
    + q0 M% J/ z6 k
39.         elif rank[x_root] > rank[y_root]:
    9 L# m, @3 a5 X1 V* o6 x2 ?( K
40. 
    ) F6 Y1 _9 Z* t% a6 q
41.             parent[y_root] = x_root
    & K5 }* U, O( i1 Z2 `1 c9 g
42. 0 z2 O\" C* _' X; }7 G  k
    
43.         else:
    6 X/ ]\" a! Q, J
44. 
    / h0 T% j; p  k2 p; m+ e: K2 Z
45.             parent[y_root] = x_root0 @, j' l3 J7 U; b
    
46. 6 i. Y' K  J' N' R3 d5 H% A1 _
    
47.             rank[x_root] += 1
    3 `, [! [) m' ?; w. {7 U
48. 
    + k5 r2 d: G. A
49. 
    ! P; c' z, o4 T# ]\" P3 F2 e/ H
50. 
    7 f- S+ H: a+ W4 B
51.     def kruskal_minimum_spanning_tree(self):# I6 F, O$ s+ f
    
52. ! w! b+ e9 m+ J( Z3 A/ l3 Z
    
53.         result = []
      g: X& N  v4 K0 f  ]! J\" I: q
54. 
    * s! t, M/ D, h9 Y/ m6 R) P
55.         i, e = 0, 0
    3 @( J4 x1 o; R3 a
56. 
    0 h, {0 ?- D. k8 I
57. 
    \" H; y2 z& \; Z
58. 
    3 @+ R\" t# n9 ]- t2 U% ^! L0 ?
59.         self.graph = sorted(self.graph, key=lambda item: item[2])* m% ?! m- d7 a! I! a0 [$ @2 x
    
60. 
    . B1 J  u* }+ L/ L
61.         parent = []
    0 s9 U( Z\" s1 d% o: W. {* B
62. # i' T1 D& O/ n8 @+ R: H3 C1 a
    
63.         rank = []
    / |/ x/ H0 c) E- S
64. # x0 z  K5 G' }1 E7 v: F' S
    
65. % C0 X) K- o* _: V  p7 Q9 R5 q
    
66. ) S8 i+ k* |( O# X
    
67.         for node in range(self.V):
    0 h) U( Y# }- R% a0 C# w
68. 
    & ?& P2 I+ I% L+ E/ a& d
69.             parent.append(node)0 p9 {7 x% ]3 k7 _/ z
    
70. ( R% |$ l( ^9 _\" t; Y3 ?5 b
    
71.             rank.append(0)0 A/ A8 v: R, h- r, v
    
72. 
    * W\" f# h! e/ W+ ], P8 p. q
73. 
    ( B* u& I, ^: I8 G; F
74. 1 o+ U1 O0 a! h5 a& T. n$ J( o
    
75.         while e < self.V - 1:
    0 M0 ^, r, Q1 k; o. s
76. 6 y7 y4 u  ~% s& m5 W' T
    
77.             u, v, w = self.graph[i]
    . A4 f0 l% k0 F+ |\" N
78. ; `! l4 d  |9 T) h
    
79.             i += 1
    / l0 e. [, N. A+ q* l
80. 
    ) G3 I$ O) L8 N; o7 D( z
81.             x = self.find(parent, u)
      A  h6 G* Y# `1 p! D\" Y5 T
82. \" r& v- F\" j$ B& R( {* @
    
83.             y = self.find(parent, v)0 \. d7 v9 ]6 f8 V# K! L) @
    
84. 
    9 ]) {5 p1 a$ J# o; K* T3 a\" m
85. 
    ) Z, z0 [' h3 q2 R& }4 T4 ?* ^) b9 P
86. 
    - ?+ G* {) m% q9 s+ l+ b
87.             if x != y:3 V* w7 [, Q1 X
    
88. 
    6 K6 X1 q/ `\" X2 ~& u
89.                 e += 1+ J# U- g' i9 m, p
    
90. 
    7 I8 M  A3 O( T7 f* e( |7 r
91.                 result.append([u, v, w])9 C5 y( y3 k. d. {) F. K' H  p
    
92. 
    4 r, q# q! v* P4 I1 C4 D
93.                 self.union(parent, rank, x, y)- N/ y& T+ H4 u2 u& `
    
94. 
    5 X  R: q' e9 u& D$ I+ H
95. 
    8 _$ @! |  C6 ~\" p- `% V' \( P
96. / S1 C! r: p/ Z\" A( g
    
97.         return result. c  Q$ w; Y\" j: c
    
98. 
    . r! B) F: k! ~4 Q! ]0 Y
99. . U+ @# Z3 \7 t( i4 t
    
100. 3 u+ {( ^) |0 [$ |1 d
     
101. g = Graph(4)2 S% h+ P0 l2 `  ]  @' L
     
102. 
     5 P0 p9 ^1 `! Y. }
103. g.add_edge(0, 1, 10)0 U* K- p; F4 }0 X. H
     
104. 
     ( K\" l0 y! B; L6 d
105. g.add_edge(0, 2, 6)% o7 u\" s4 h' b# j' C* a- q- o
     
106. 
     ; N2 M( A! U7 {% g# y4 K5 ~* ^% X
107. g.add_edge(0, 3, 5)1 c. H+ \8 o6 U0 g
     
108. 
       R4 w3 A0 m: b3 j  o& y8 e0 w) \
109. g.add_edge(1, 3, 15)
     , K& V\" ]. M3 o+ S/ y2 B2 r
110. 
     5 Z: x0 r3 f, S+ N( L
111. g.add_edge(2, 3, 4)* }\" B8 _+ X8 y/ T0 g/ G4 o
     
112. 
     ) ?. l  B2 a: Z6 N* ~1 j) g+ Q
113. ( K; V8 I' ^0 u2 Q7 [% D
     
114. 
     - [7 J8 m9 [5 z; K. e
115. print("最小生成树的边:")1 l# O+ m4 j) s- K3 L) t
     
116. 7 ?& d% F- I( f
     
117. print(g.kruskal_minimum_spanning_tree())

复制代码

这段代码定义了一个Graph类，其中包含添加边的方法、查找节点的父节点的方法、执行并操作的方法以及使用Kruskal算法查找最小生成树的方法。
9 Y! `, v9 H1 d: k" a$ Q& M! t