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

2744557306

Kruskal算法是一种贪心算法，用于找到连接的加权图的最小生成树。它找到了一组边，形成了一个包含每个顶点的树，树中所有边的总权重被最小化。
以下是Kruskal算法的简要概述：
2 t9 f. t- t: q1 e7 R- C7 a
% @' Q2 q% J: P, S* }0 J1.排序边: 将所有边按照权重的非递减顺序排序。
2.初始化: 创建一个森林（一组树），其中每个顶点都是一个单独的树。
3.遍历边: 遍历所有边，从最小权重到最大权重。
4.检查环路: 对于每条边，如果将其包含在生成树中不会导致环路，则将其添加到生成树中。否则，丢弃它。
5.合并: 如果将边添加到生成树中，则执行合并操作，将两棵树合并为一棵树。

6 ^6 i; m2 k) Y6 s: _以下是Kruskal算法的Python实现：

1. class Graph:3 [% Z1 C5 g3 K\" D4 \  F
   
2. 4 }9 M# w3 J8 ^0 w3 W) j
   
3.     def __init__(self, vertices):
   6 [/ a2 T. g  E1 ~# n$ }
4. 
   2 t* O& q: c\" w4 c! K. M5 E
5.         self.V = vertices8 |) k* ^! s. C: o
   
6. 
   9 v; y+ r% }/ r\" y5 u1 J
7.         self.graph = []
     d+ S$ W  p$ }4 h% Y7 K
8. 
   5 i1 e& ]% ]' k% K9 t2 w- }5 x\" `) h
9. & y. E3 u1 ^5 n8 u+ ~
   
10. % B5 g9 y: A+ T. `! B9 Q+ l
    
11.     def add_edge(self, u, v, w):6 u# X$ H6 k8 K' ^5 O9 i& R
    
12. 
    ; q: g5 j. F% D3 i  p
13.         self.graph.append([u, v, w])
    1 I% i2 n4 u9 B# M
14. # P1 n/ ~& j0 ]; J9 R! L
    
15. 6 @) b\" G( N+ u
    
16. 
    ! s) s2 x5 m( M
17.     def find(self, parent, i):
    ! v  j, d- r7 I( O) K- r
18. 
    ! `, P. Q2 X$ n& G9 J
19.         if parent[i] == i:
    6 L& f5 z$ B* l; x: ~, o: z) M
20. 
    / f* c, ?  I\" [* N: e
21.             return i
    1 i3 ^/ u% Y& E\" r
22. 
    9 \2 E: J8 |$ [\" T1 s6 P7 W0 W
23.         return self.find(parent, parent[i])
      w\" f\" K! F* V& ~
24. . m7 B+ r- w: R) |3 T6 a: u, z' L
    
25. 2 I* A. Y% \) f  h& v
    
26. 
    4 P! z1 M2 a1 ~% @
27.     def union(self, parent, rank, x, y):
    \" ?6 U: c; Q$ q# f2 J
28. ( S\" m2 e, g3 O$ x' r1 o3 {3 e
    
29.         x_root = self.find(parent, x)
    ( v6 ]0 B) n* ~8 l
30. 0 Y) |- |( A' X! \\" ~: c
    
31.         y_root = self.find(parent, y)
    $ V( y/ W; p\" \' I$ E: I
32. 
    0 E\" @8 v% A0 Z* R7 Q: X
33. 0 K# B$ E& n2 L' {. i  u0 g9 d4 B
    
34. 
    2 Z. D! P& W. e! t; O6 C1 H9 ^
35.         if rank[x_root] < rank[y_root]:: [6 w( _7 r! w7 D0 ^/ ]
    
36. 0 [. X! g' x) z* @9 R! d
    
37.             parent[x_root] = y_root
    $ U# R3 ?' [& {4 V* d: s
38. % F, j  f7 {6 `: c( x2 \. w2 q/ n
    
39.         elif rank[x_root] > rank[y_root]:
    1 P  j( _8 \& b/ s$ v# X7 h3 ]6 g* M
40. 
      f$ }1 N: R9 I\" c
41.             parent[y_root] = x_root( R6 t+ h* [7 e: o
    
42. # M% r/ ?8 L1 f0 l$ h+ C
    
43.         else:. @: l/ g* ^; C- P. o; f! A6 o8 b4 M7 l
    
44. 
    & G* H2 A6 ^4 T$ `
45.             parent[y_root] = x_root
    , _3 O6 o& N3 t) g. d. `# g) s
46. 
    2 M1 `. T8 G) F
47.             rank[x_root] += 1/ ]% k$ a3 n8 _2 n
    
48. 1 c! n7 z  B8 [
    
49. 
    + N, H+ o: ]& j  T* ?- E
50. % \% Q* s. D9 R/ H
    
51.     def kruskal_minimum_spanning_tree(self):. m; j$ j- k! `% c* H6 p, @; _
    
52. 
    ( H, o# j# f* {5 O; d\" }# d! W
53.         result = []3 C* L4 N4 k( b' H+ c
    
54. 
    # H& [( e' \4 o. @; U! H5 `
55.         i, e = 0, 05 s% y) ?. X1 J- }' V
    
56. ) _/ p$ o8 u. Q
    
57. 
    / b2 T; S! O5 ?% t& v- ?% T
58. 
    7 P2 B. ~. ^- q- J/ d4 v
59.         self.graph = sorted(self.graph, key=lambda item: item[2])9 ]! |1 }2 O3 ?\" Z* ]
    
60. 5 q& E3 S3 L7 s% r+ e9 w# x& u2 z
    
61.         parent = []
    ' e9 R- Y. U! ^$ m  t
62. 7 I) o  s9 Q/ j: n\" l# O9 I
    
63.         rank = []
    4 G* Q, j( j, g! a) F' w) [  Y' [
64. 
    6 M9 A( h' P4 Y' r& O
65. ) |% f# K/ N0 P4 L3 x
    
66. . [' C, F0 F\" A! [+ s9 o
    
67.         for node in range(self.V):
    \" o$ J\" m* E4 D. Q6 S* ]5 D- Z) o3 t
68. 
    2 n* }& X  \& n& l3 ^
69.             parent.append(node)
    : e! M( g/ a: T- F, x3 }2 |6 ^
70. 
    # }6 q$ G* c! O4 ^\" _: v% z. n: K
71.             rank.append(0)# G# [7 I8 Q% q6 W- ]1 m& O
    
72. 
    ' i8 f\" f) N' b2 {: c
73. ' p; D5 A& R3 H# i* k! h
    
74. 
    ( O, @. ?/ e( D
75.         while e < self.V - 1:
    * Z, \- i) W\" {
76. $ A) }1 w8 f$ f+ \$ r3 u
    
77.             u, v, w = self.graph[i]3 c& I4 J% ^/ g5 M9 c
    
78. 0 @. K, n3 [5 h- a7 {8 F5 U
    
79.             i += 12 \5 S5 D2 W' y( q$ c+ P2 c
    
80. . @) i% q2 ?2 e6 F\" h* E! F
    
81.             x = self.find(parent, u)
    \" E$ T3 n; x0 J8 A6 R- e
82.   ^+ ]1 `, D/ {- E4 b2 {% ^* a; e
    
83.             y = self.find(parent, v)) _8 w% L, H% V! m# A6 ]& B
    
84. 
    . K3 O; `6 F+ \, Z/ m) w9 s* n: X
85.   q& H* X2 y# [3 \9 {: y
    
86. 
    9 V% `; L\" O: y& h3 G
87.             if x != y:
    4 L) Q\" I& A0 w7 o' {( p
88. 4 d/ p/ q0 E8 R! V2 i' U. S$ t
    
89.                 e += 1
    ! E2 x/ @6 b/ p, p( h+ q: Y
90. ( D# h1 J2 T, i# E4 Z
    
91.                 result.append([u, v, w])+ e! @4 d6 E2 {3 I+ o# d  ?
    
92. / H: z- Y1 u  r3 D( D6 i# [
    
93.                 self.union(parent, rank, x, y)5 H/ N/ F, Q0 A+ ^\" n, Z
    
94. 7 ?/ a/ M& _( M; v1 Q5 g
    
95. 
    3 S- k# u7 n& W, I
96. 
    ; ~, _4 N5 J$ c- p1 l% g. C
97.         return result\" c) h; Y- a0 u  t$ N
    
98. 
    2 w0 a% K3 i' m& J* r' m2 {
99. 2 T$ T+ g$ B. S8 @' ?( J: N
    
100. 7 l0 k3 [0 S# O( ?1 n+ t0 A
     
101. g = Graph(4)
     1 h6 u) y0 h; M' v$ W% h; O8 m
102. + |! v6 l+ B! i. ^) U7 a# A7 D
     
103. g.add_edge(0, 1, 10), `- v% I1 [1 \- ^+ O0 h
     
104. / v* [( @0 D3 x* f1 G& V( [
     
105. g.add_edge(0, 2, 6)
     . \6 b\" k3 D; W4 L4 y  u
106. % H% A\" G2 w3 L% ~5 Z4 e
     
107. g.add_edge(0, 3, 5)
     * W' x8 [1 t* ^* F! m
108. 
     8 ]% v8 }9 M: q# ^2 m
109. g.add_edge(1, 3, 15): B2 Z$ j- C. Z7 f  z8 y3 o
     
110. : \7 f8 p; m4 _5 U# _3 u
     
111. g.add_edge(2, 3, 4)
     6 w2 h/ y' i; K* ]
112. 7 N7 @; O9 x& X0 Y8 {
     
113. 
     0 s, Y; \+ v/ n. K
114. 
     \" w  N- t) P+ c* L& O9 b
115. print("最小生成树的边:"). p5 j5 c) {  l0 b+ g( Y3 j; [
     
116. , w8 c( H. V3 M' q0 t
     
117. print(g.kruskal_minimum_spanning_tree())

复制代码

这段代码定义了一个Graph类，其中包含添加边的方法、查找节点的父节点的方法、执行并操作的方法以及使用Kruskal算法查找最小生成树的方法。
+ G6 A/ i  {% a4 ]) _; I. K
5 I0 C' Z( g/ X' E+ J( [1 Q