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

2744557306

Kruskal算法是一种贪心算法，用于找到连接的加权图的最小生成树。它找到了一组边，形成了一个包含每个顶点的树，树中所有边的总权重被最小化。
以下是Kruskal算法的简要概述：
/ C: G& y7 G5 d; l( `
" ?, h) F- U. C3 n  @1.排序边: 将所有边按照权重的非递减顺序排序。
2.初始化: 创建一个森林（一组树），其中每个顶点都是一个单独的树。
; S; U/ j1 N5 E+ H8 H9 t  T1 D3.遍历边: 遍历所有边，从最小权重到最大权重。
2 m$ N3 [9 J8 o+ `; @3 v' P4.检查环路: 对于每条边，如果将其包含在生成树中不会导致环路，则将其添加到生成树中。否则，丢弃它。
) o- p, V1 i0 I' S# R1 k7 s: f. b. X5.合并: 如果将边添加到生成树中，则执行合并操作，将两棵树合并为一棵树。

  c6 X- W- K& z- Y* Z+ `$ [. E以下是Kruskal算法的Python实现：

1. class Graph:
   & J# X3 I( B+ H\" c' c
2. 3 `. w6 z, C* I7 y  W! F: o+ f. r
   
3.     def __init__(self, vertices):5 |: H\" L. Z2 ]+ E
   
4. 
   $ f/ u8 c' g, G# ^8 e
5.         self.V = vertices  N4 g+ j0 p) h6 `
   
6. 
   , X7 ?7 U' V3 @9 J* I
7.         self.graph = []4 w, \( J7 k4 X9 |( g7 W: X
   
8. 
   / w8 [\" r* ~  x/ L# t
9. , q1 y' K8 G0 b* ]) H
   
10. 5 P& L1 G3 y9 O- Z
    
11.     def add_edge(self, u, v, w):. ]$ P: r$ ^) X3 {* f* i. b
    
12. 1 g3 u: [6 E  \% Y* h- g
    
13.         self.graph.append([u, v, w])
    ! x3 |3 P/ J# ~& n4 N$ m) N0 e
14. 
    ' z3 s\" t0 C* k: K9 Q4 A0 q\" K3 J
15. - o1 z7 F+ z, G\" |8 l, F' a2 \
    
16. 
    9 y9 U( G6 O\" g
17.     def find(self, parent, i):
      f+ I  U; h. q9 f. @9 A
18. 7 _1 c5 V( J! w+ z
    
19.         if parent[i] == i:
    ; y- L. N1 T. c; ]$ ^
20. 5 t, g4 c% t- n) T- L% a
    
21.             return i
    / e% k\" o% t' N8 Z% \: l( `' I% A
22. 
    ! o0 H% a. O9 v& G
23.         return self.find(parent, parent[i])7 S1 _) j$ y+ \' V1 o
    
24. 
    8 ]( [) c3 Z* W: y
25. 
    ' q1 [9 i5 s) ?9 K3 w
26. * C5 s0 g+ X5 M, N/ ?2 t
    
27.     def union(self, parent, rank, x, y):
      I& n: b8 e1 s8 h  ?  ?
28. + h' _+ A& h( V! v0 C, ^4 ]
    
29.         x_root = self.find(parent, x)1 K$ A+ e9 D/ f  [9 d; y
    
30. 
    9 Q) H( V& `\" u! R
31.         y_root = self.find(parent, y)5 M# B# G\" j# f0 o( E% G
    
32. 
    * l4 e5 i1 X& D, }+ m* M
33. 4 i  b5 ], j# o7 S3 S
    
34. 2 _- ]\" E1 M( F* y3 t6 h) Q
    
35.         if rank[x_root] < rank[y_root]:4 V$ d, y5 j# D% |# e8 \+ C
    
36.   [4 D: F\" w' u
    
37.             parent[x_root] = y_root\" m8 ~  a2 d& Y' [; O' n5 j2 @$ n: z
    
38. 
    ) P- V7 ?- _- E% S. U# D: k& @
39.         elif rank[x_root] > rank[y_root]:) J  S; g  ~7 ^6 I
    
40. 
    , b/ Z! Q, b4 I' }' G/ _
41.             parent[y_root] = x_root  V# q% M# p6 E# _0 N. i+ h5 q5 H9 w
    
42. 
    : w  Y0 E  ~2 ~8 J0 R
43.         else:: |  J3 O: w- ]
    
44. 6 p' q; N& y1 u  G) z% p5 P  K: [! d
    
45.             parent[y_root] = x_root& S1 ]\" x\" b- A
    
46. 4 h# v4 h: R2 W  W  U3 W  p$ v- O! Q
    
47.             rank[x_root] += 1( T+ E! i7 ?4 P/ R( ~
    
48. - z* H\" z* S  u4 i. C5 f
    
49. 5 P/ O- D; y; N! [5 `* B; P
    
50. 
    , i: h: O6 j* N\" @; S0 j: i
51.     def kruskal_minimum_spanning_tree(self):
    ( ]' @0 \: A1 D3 ^7 n: V: t/ B8 I. A
52. ( j' K( K, ~2 {9 j4 V
    
53.         result = []4 L. c/ g$ [# }- j  V4 w+ [$ Y
    
54. ; U' B( ~4 L# o$ L: s
    
55.         i, e = 0, 0* U\" n. d7 s8 f' m& v
    
56. 3 H  H5 Y& E' H5 S- {7 X4 \: ~/ A& k
    
57. 
    9 Y9 ]7 C2 c, h
58. 
    3 D- G. Q9 x: e
59.         self.graph = sorted(self.graph, key=lambda item: item[2])
    7 c7 @/ `5 Y4 _( O% [5 |! W& t
60. 1 Q. z: b* O' p9 W* h, O! X
    
61.         parent = []
    % v9 P1 _- P; u\" L+ n& }6 f. z! R+ f
62. 
    9 ^; f6 D4 S# d/ P\" b! ?4 Y# p
63.         rank = []: U* T6 Q1 P! x0 E3 P\" c% A
    
64. 
    ' g  O3 B$ F  K, T
65. 
    : y\" z: `8 Z1 p
66. 
    ( c' q0 F; n$ h4 r8 k$ Q
67.         for node in range(self.V):\" r  {# ~2 Q; }) R4 a2 \3 D6 e
    
68. 
    8 |% k9 _8 _/ z
69.             parent.append(node)
    $ W; ^/ q( n( f( V3 o\" O
70. 
    ! i7 L4 ]5 @, G  p
71.             rank.append(0)\" x4 s8 H! M' P8 W\" }2 S- j, J( W# a. \
    
72. # `% z  I6 o; c: f\" Y4 J3 p' y
    
73. 4 j' D0 ^' _9 Q; ~- ^
    
74. , `2 N+ X. G% L: r3 [
    
75.         while e < self.V - 1:\" |6 M* y! ?1 x+ z7 ~2 S
    
76. - i8 Z  c: x0 }0 Q# Z, z
    
77.             u, v, w = self.graph[i]
      ]  C4 |) }4 f7 u. |
78. % [. J  ~7 K: A! ]8 c' S  x
    
79.             i += 1
    % _( s) [. E% ?& R) {% V, g* u: U9 P
80. 
    : I7 F0 r' z# |  ~9 k
81.             x = self.find(parent, u)- Z  U3 p4 Z( {7 S4 ]
    
82. 
    4 ^+ G2 V  S! V4 s  J
83.             y = self.find(parent, v)7 Y& s9 A8 M* U; Q
    
84. 4 p: f8 f7 K  [* Q
    
85. 9 K8 V( u; h# ]9 u/ y1 P7 K
    
86. 
    ; E% g8 Y& ?; z2 Z9 d! n6 Y5 d
87.             if x != y:5 [8 C3 x- B5 h, f5 B5 A! V4 p
    
88. 
    0 k0 h+ o9 K3 v
89.                 e += 1
    3 p& e! o\" [3 `3 ?
90. 
    ) l- ^  j# K. d
91.                 result.append([u, v, w])
    9 E- l( p( Z1 g% U7 V' L$ ~6 U7 W
92. 
    0 Q; T+ a. o. M( ]/ W+ Q2 ?, L' u
93.                 self.union(parent, rank, x, y)
    6 F& F+ E3 ]) _' n
94. 
    ' h# B  }8 F1 \9 m' F
95. 
    * k: g7 N) D2 W  n! S, f* Q; J' X
96. 
    % y( f- l& @5 N
97.         return result
    ; H) y) `# ]% J5 ~5 W* p7 `\" O
98. 
    - Z$ M1 s( S) N) |
99. / _8 w/ X\" p1 T& _
    
100. 
     5 _9 Q  K0 ?9 h4 g
101. g = Graph(4)4 S  k/ p3 F2 H8 @
     
102. 
     8 m- ~- s9 P, u! e- t
103. g.add_edge(0, 1, 10)
     # B' Q: l1 p/ ^% E$ e( F/ m/ m( B( \4 I1 V
104. 
     . K$ @$ m  R0 w' \! }2 H  S\" \
105. g.add_edge(0, 2, 6)
     4 I( G  A# `- e7 l  J; p9 |5 m
106. 
     ) }7 r' Y0 v! g/ t, o
107. g.add_edge(0, 3, 5)% D/ ?7 Y8 S' F0 M
     
108. . R4 I& Q/ I& s+ ^: m. J
     
109. g.add_edge(1, 3, 15)
     % a8 r, ]- |' l% C\" ~5 P2 V+ P) ^
110. 
     0 \7 h6 e* Z7 Y. t2 t, [
111. g.add_edge(2, 3, 4)
     ! W) ]; S) k7 K0 q9 t
112. + f( R/ \\" ^2 Y1 T0 d  Q2 R, H! p, G: d
     
113. , k! q2 X9 J/ O4 E
     
114. - |5 X6 ?1 e& D6 q' d
     
115. print("最小生成树的边:")* ?+ U; o! X# n
     
116. 
     / t+ v' Z: r  K3 {% c
117. print(g.kruskal_minimum_spanning_tree())

复制代码

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