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

2744557306

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

1.排序边: 将所有边按照权重的非递减顺序排序。
2.初始化: 创建一个森林（一组树），其中每个顶点都是一个单独的树。
3.遍历边: 遍历所有边，从最小权重到最大权重。
4.检查环路: 对于每条边，如果将其包含在生成树中不会导致环路，则将其添加到生成树中。否则，丢弃它。
5.合并: 如果将边添加到生成树中，则执行合并操作，将两棵树合并为一棵树。
8 k- J* M9 Q& S* q  N/ O, Q8 u
4 y6 e' ^4 q- X) @2 t% ~1 ~. s  T以下是Kruskal算法的Python实现：

1. class Graph:' X$ E' i) I, x! o+ l
   
2. ; m' B+ Y8 ^% G$ Y7 A4 `- B) W
   
3.     def __init__(self, vertices):, c& C3 h7 E) T+ E( ^
   
4. : l  {8 q, K; ?$ ?  c' \6 Z
   
5.         self.V = vertices# ?- ]  G+ b+ a
   
6. 
   , j8 V2 [& a* D
7.         self.graph = []; v0 O( e( x$ J8 r
   
8. $ {6 A1 Y6 y+ @
   
9. 
   $ ^# B1 `( f. ~\" d
10. ' g# i& E4 J+ ]
    
11.     def add_edge(self, u, v, w):+ S: L9 p- M2 z# [
    
12. 
    3 R. }' `( @/ Z4 u, A
13.         self.graph.append([u, v, w])0 O5 y# @( Z' e7 l
    
14. 4 P% |; b\" h. _6 Q
    
15. 
    * O: d- W7 `; Y% z! f# H+ Q7 W
16. 
    2 A) r% I# v\" Y. V% X& s
17.     def find(self, parent, i):0 d/ [! ]& w' ?% M6 ]( N, O
    
18.   h9 u; B- V! J; O1 q0 c
    
19.         if parent[i] == i:
    6 G+ C: G1 V: h: `; x8 z2 `
20. 3 }\" P  B0 _: j. L6 a, @* N+ Z
    
21.             return i
    + L) M$ X# \\" X+ c
22. 
    * \# N1 D2 S; T: B; ^4 K* i5 _( a5 K
23.         return self.find(parent, parent[i])
    4 Q2 h6 c7 W9 O8 \0 P  M
24. ! t3 [6 g3 G3 U' L1 s: d* i
    
25. 
    5 I5 C4 W$ ], R5 j% m
26.   J% G% E. R/ o0 M! _1 w
    
27.     def union(self, parent, rank, x, y):5 w8 M8 ~\" J5 Z$ a( s
    
28. 
    ( h8 d; F9 |, q! D; l
29.         x_root = self.find(parent, x)0 i2 w+ G5 X; S8 X0 s# S, I' E; G
    
30. $ X6 W' B4 p/ D- R
    
31.         y_root = self.find(parent, y)+ a\" k  f/ P0 O7 Q9 u
    
32. ' I, \- ?) h4 @! X
    
33. 
    6 p\" q9 d4 P8 ^$ A\" v+ v7 f
34. 
    ! k# g, F0 G+ T5 y
35.         if rank[x_root] < rank[y_root]:% e$ z+ {2 A# Q5 I( R3 p
    
36. 
    . R) Q% z9 e. z; u: n
37.             parent[x_root] = y_root
    . ]. A, l3 V1 n\" q
38. 
    1 Q) m+ W5 d+ x
39.         elif rank[x_root] > rank[y_root]:
    2 q) O9 g$ x! ~- O4 r6 i/ y
40. ( K- B1 i3 Q- B# I6 H
    
41.             parent[y_root] = x_root: c' \5 q4 F, R4 f4 M: g8 M
    
42.   c2 s  L6 H2 `  ?9 P4 m
    
43.         else:/ G2 k, K% G\" a\" W% V) q
    
44. 9 |9 J1 \  r; W1 y
    
45.             parent[y_root] = x_root' e+ y* B8 S1 r. E( }
    
46. \" I0 u6 X4 o5 o
    
47.             rank[x_root] += 1
    % f9 g9 Q1 }3 f. c: I4 |0 a
48. 5 n0 p5 p- Z: t\" j6 s
    
49. % R2 u* z4 {' h6 Z' i
    
50. + X) ?9 ?0 H& J& a. x- |
    
51.     def kruskal_minimum_spanning_tree(self):
    ' C5 E3 s% N9 G% @' H3 A+ R( z
52. ) W0 J  w8 K9 `( J9 D: m' c
    
53.         result = []
    2 c0 q! ^# S8 W7 }1 O& d& M
54. 
    . ~: b* _6 U$ l# r6 j! W- g1 S4 z1 b
55.         i, e = 0, 07 _1 l# {% i, W2 ^' m( X9 ]
    
56. . L  e) U, }3 B! r
    
57. 8 E4 w9 w7 e% z5 |
    
58. 5 ^% h( l\" G/ Q& R, K8 u
    
59.         self.graph = sorted(self.graph, key=lambda item: item[2])  {6 [; [& K: A\" s0 q5 Q* T
    
60. 
    3 u. ~; ?0 L3 f' z% f6 f9 z
61.         parent = []
    % W# I) b\" ^& b* j) R. E; o# F1 u
62. 9 n; [% x( J5 ]& P
    
63.         rank = []
    $ M( c% Y! n% D0 o% _
64. ! Z6 w- E) U. Z8 M& Z
    
65. - F; u- [\" v. Y* G
    
66. # d) M* m4 a% F) M
    
67.         for node in range(self.V):4 i5 N9 s/ y; n' }
    
68. 
    # b5 k  \( \& h: l6 W+ F
69.             parent.append(node)/ z4 I( g2 |' H
    
70. 
    ' T* P\" g' p- B: M; ]( M
71.             rank.append(0)9 _$ h\" O2 U7 A; z9 f) H
    
72. 
    $ \& z! c+ p! W& n
73. 
    + }; |* G5 T0 E/ M- B
74. 
    8 k6 A* Q' y9 N8 S
75.         while e < self.V - 1:
    : G5 l: Y, X9 E+ g
76. 
    3 r2 t\" Y% _: A! D/ G+ R% A: {
77.             u, v, w = self.graph[i]
    ! a\" k* o$ l/ D: x; r4 Y
78. 
    - S2 v' X' N8 L
79.             i += 1
    9 a6 K4 c3 O, _3 N8 k
80. 
    : U% i& X, ?) e5 e. F  ?7 c
81.             x = self.find(parent, u)7 X# V5 f0 I4 p8 j
    
82. 
      g( Z  u% X# G: i\" s\" f
83.             y = self.find(parent, v)
    % ~& W( R. H7 P- j# w
84. ; I8 y# |' w. P- Q. R/ m( X\" B
    
85. 
    0 Y% w- e3 ~! O1 T- @5 P
86. 
    $ O: I  ~* H8 W3 r. n
87.             if x != y:
    $ e. a8 ]$ e. b( E% Q
88. 
    # n6 v, W& j1 x9 m
89.                 e += 1% {; A/ }% V$ Q* \2 G( X' }1 s- w2 t' D
    
90. : y0 K' ~4 b$ `$ y$ \9 X4 G2 ^
    
91.                 result.append([u, v, w])+ D3 H( s7 ?! A/ `
    
92. * k$ x2 b  {# _$ O$ e
    
93.                 self.union(parent, rank, x, y)
    2 v9 [3 q$ q4 A' u* ^9 v4 h
94. 
    ' p7 S7 h- K  ?7 T; \
95. 3 z* B+ U! V! A6 l\" o
    
96. 3 ?# D+ a\" Y1 A* C9 @( l0 m0 k/ r
    
97.         return result
    9 n- i* I- Q9 T/ l7 v, R5 O
98. 
    ! Z, U0 t6 |0 \; U6 |8 B2 c
99. - o4 j' F' U; l* P! P' g# [+ p
    
100. 
     $ e' I6 k; M8 M, r6 g7 m  A- d
101. g = Graph(4)
     0 G9 O  Y' R2 u- n# h
102. 
     7 G( v\" v6 S# i\" z( O( k0 s
103. g.add_edge(0, 1, 10)) c. q, ?+ e2 O) p  Q- l
     
104. 
     * ^9 l. {: q1 k7 e
105. g.add_edge(0, 2, 6)
     ! P- P8 \5 |* l# f  r
106. , y$ S# P& ~, M. P
     
107. g.add_edge(0, 3, 5)- j$ F6 [! G& @8 E7 T
     
108. 0 ^$ r' E% J8 j: V, Q
     
109. g.add_edge(1, 3, 15)! v6 p6 k- F/ X% y1 y\" x
     
110. 
     - Y. ^. O) b\" r! P7 P) R6 {4 a. I5 Z\" i
111. g.add_edge(2, 3, 4)
     / ^7 e3 j/ j$ N/ U$ [\" @' |- L
112. 
     4 X6 w* [2 J4 P8 l9 g, W
113. 
     $ o2 [5 a. Z; ?5 B\" k) k
114. 2 I$ W9 K% {7 E
     
115. print("最小生成树的边:")3 B( n0 O$ W& @4 s3 u7 H1 D. W3 W
     
116. ; r8 M3 t) B3 x! G
     
117. print(g.kruskal_minimum_spanning_tree())

复制代码

这段代码定义了一个Graph类，其中包含添加边的方法、查找节点的父节点的方法、执行并操作的方法以及使用Kruskal算法查找最小生成树的方法。
8 h& H5 m7 R2 Z5 h
7 i( T8 \0 y1 ^7 k3 c# e1 [" v
2 z. }; a- l7 }7 p+ l* G/ C