Kruskal算法C语言中的实现

2744557306

Kruskal 算法是一种用于寻找最小生成树（MST）的方法，适用于加权无向图。其基本思想是通过边的权重来逐步构建生成树。下面是 Kruskal 算法在 C 语言中的实现示例，包括必要的数据结构和完整的实现过程。

  _! z% _- \9 I### C 语言实现步骤
8 W2 |: {% p0 S+ b9 {1 ?; R9 o2 y
1. **数据结构**：
   - **边（Edge）**：表示图的边，包括两个顶点和边的权重。
   - **并查集（Union-Find）**：用于管理和合并不同的集合，以检测循环。
8 H! Y5 f' \4 W9 j
  U" t5 H7 d$ i' k2. **算法步骤**：
( h4 ?3 B) m$ I4 T" O6 S   - 将图中的所有边按照权重进行排序。
/ H% X: X$ i" k   - 使用并查集逐边检查，如果两个顶点不属于同一集合，则将这条边加入最小生成树中。

### 完整代码示例
9 c; R* k& ?8 u/ l3 ?, l
以下是 Kruskal 算法的 C 语言实现，包括必要的函数和并查集的实现：

1. #include <stdio.h>  
   * H: b% H9 {  V, h
2. #include <stdlib.h>  1 K, S/ g% z, m, L* H; G' Q
   
3. ! d; g. I& J8 s: N% U& y' ]8 O$ @
   
4. #define MAX 100  4 G  t1 d+ R/ g4 `
   
5. #define INF 999999  % U4 G9 |9 k* F5 Q: M  u
   
6. 
   ) n8 v' \- x* G% H# a  e
7. typedef struct {  
   ! i% R& \  \; q\" k- n5 M+ G# S
8.     int u, v, weight;  
   # g3 Y/ w& T$ W: s6 |0 ]7 l; a7 ~
9. } Edge;  \" U9 K& H' I, @2 ]\" y8 \
   
10. . L7 G+ k9 L* U5 {4 ^5 L
    
11. // 并查集结构  
    ( w1 W+ A( L1 g1 `) \; _
12. int parent[MAX];    e$ ~0 u. ^5 K' g
    
13. ( |# T1 d% g3 f+ _
    
14. void init_set(int n) {  
    5 D2 L$ a' l- p# j2 t. L
15.     for (int i = 0; i < n; i++) {  1 P3 H5 ]0 v/ G1 ]3 r' y
    
16.         parent[i] = i;  6 g4 H3 ~: B& S6 _* m. G/ H) q
    
17.     }  9 V% g8 B* O! s$ }3 S. G+ B' P
    
18. }  : D) x. \8 ]3 d  z: O- R
    
19. 
    8 e3 ^4 X$ x2 l* j
20. int find(int u) {  
    . j) k* \! h6 F: P' ]
21.     if (parent[u] != u) {  1 _3 v. e0 v- a+ l  G& z
    
22.         parent[u] = find(parent[u]); // 路径压缩  
    ' S) O- O1 @) s
23.     }  
    / d) b# ^4 f! s# K4 E/ W8 ?. c
24.     return parent[u];  
    / L( Y& t9 D\" m+ n+ r
25. }  
    ) R- P  D, y; \3 l9 l- c9 a& z
26. 9 b1 K$ |\" Y' ?
    
27. void union_sets(int u, int v) {  + y5 ^% I9 I: y7 \# H5 V% B
    
28.     int root_u = find(u);  % Q( ]) h0 ?$ S# x
    
29.     int root_v = find(v);  
    ; T& Y0 G8 f; e
30.     if (root_u != root_v) {  
    4 B3 h2 t& u; L4 z6 L
31.         parent[root_u] = root_v; // 合并集合  / r6 U5 ~9 x6 ~! }- W( v
    
32.     }  
    & o9 N; i: n3 ]8 R
33. }  
    ( ^# J9 q, \1 W) @/ Y
34. 
    ! p! I& h, R* w4 w, X* T
35. int compare_edges(const void *a, const void *b) {  * ~5 v; s' n/ `2 w# I; d8 ?
    
36.     return ((Edge*)a)->weight - ((Edge*)b)->weight;  \" a9 ^$ v! F& u
    
37. }  ; [6 Z. f' {. e/ b
    
38. 
    # ]5 X5 u# ]; |9 o
39. void kruskal(Edge edges[], int edge_count, int vertex_count) {  
    1 x  v# x0 g% Z9 g
40.     // 初始化并查集  1 C  ]8 \$ B. d5 Z/ i/ j; a5 M
    
41.     init_set(vertex_count);  * k. B9 H! Y/ I\" R5 ~
    
42.    
    8 \& \5 u9 e) }4 T
43.     // 排序边  
    \" M9 @\" `5 @+ J3 }% O\" J4 k
44.     qsort(edges, edge_count, sizeof(Edge), compare_edges);  $ b  h$ f' \0 K# ^- t
    
45. 3 h# o( \' x/ G\" O) L\" [; L. e5 z
    
46.     printf("Edges in the Minimum Spanning Tree:\n");  , S) A& K5 Q  y
    
47. ' z6 [# ]: f* O
    
48.     for (int i = 0; i < edge_count; i++) {  ) d4 z# e$ J( c5 a
    
49.         Edge edge = edges[i];  $ L& H/ e2 m' D+ T2 y' H
    
50.         if (find(edge.u) != find(edge.v)) {  ( X# D& s! B% [% R. I* C
    
51.             union_sets(edge.u, edge.v);  
    - E7 Q; A8 |% N& z' e
52.             printf("%d -- %d == %d\n", edge.u, edge.v, edge.weight);  4 W( i. W' @1 [+ S
    
53.         }  
    % {9 }$ a' K& i$ U$ H1 T, Q: q  o
54.     }  4 |1 L! G\" u3 \6 S9 j
    
55. }  ; W+ I3 g! P1 B  q0 c4 k3 h
    
56. 
    ) {# k8 r: X! u' |& R, W8 Z; l
57. int main() {  ' q9 N9 T+ H6 B  n
    
58.     int vertex_count = 4; // 顶点数  
    ! @# S% {* y# W) }! h5 l( _- B2 c
59.     Edge edges[] = {  , v/ O6 n! T% u/ H  s
    
60.         {0, 1, 10},  4 E, Q/ {8 R8 d( F5 `, b2 f, S  S
    
61.         {0, 2, 6},  
    9 B) B2 p$ |5 c  v  ?
62.         {0, 3, 5},  2 a/ B6 D9 R$ ?\" ?' _6 `
    
63.         {1, 3, 15},  ! q% r$ O# _: R\" W2 v# j
    
64.         {2, 3, 4}  3 B7 y- G1 S  h* A! {& _1 z% t
    
65.     };  
    + `4 X. i. T/ {) d4 h# ?% c2 g
66.     int edge_count = sizeof(edges) / sizeof(edges[0]);  : O9 X! E% C8 @: Y
    
67. 9 x4 t+ E$ j3 S5 z+ \
    
68.     kruskal(edges, edge_count, vertex_count);  
    2 z* ^; A7 D2 y% b! ^' j\" \4 L
69. 7 F4 z3 ]& }7 j2 @, Z  i& x
    
70.     return 0;  
    / P$ A' ^7 `  X' s
71. }

复制代码

### 解释代码

1. **数据结构**：
   - `Edge` 结构表示图的边，包含两个顶点和边的权重。
- `, W' d& q/ ]( @5 \
0 h5 I+ V( B) L6 c2. **并查集操作**：
: A0 @1 r& M, e2 N4 y5 ^9 v   - `init_set`：初始化并查集，将每个顶点的父节点指向自身。
   - `find`：查找某个顶点的根节点，并进行路径压缩。
   - `union_sets`：合并两个集合。
+ X' b1 ]1 E6 G! Z* m, _6 ^5 @
3. **Kruskal 算法**：
: @) O, g8 f/ a" V0 ?( _0 J: E& [  x   - `kruskal` 函数首先初始化并查集，然后对边进行排序。对于每条边，检查其两个顶点是否在同一集合中，若不在，则将其加入最小生成树。
. B- U/ N* b1 e- h8 ]% {$ c- g
4 S. }6 j% @6 Y$ a# x4. **主函数**：
( m( `' L( Z/ B6 S   - 创建一个简单的图，调用 `kruskal` 函数并输出最小生成树的边。

2 C+ u6 s2 P( _5 H2 q### 注意事项
7 V7 w; b; x. a0 _  K- p% [8 ~- 确保在编译过程中链接标准库，适用于小型图。
- `main` 函数中的图是手动定义的，对于大型图，通常会从输入或文件读取数据。

0 Q. }6 w. w' G! a$ h0 T( M* ~) l### 总结
0 C* I) ~* x1 v1 J) `Kruskal 算法实现的关键在于有效地使用并查集来管理图中的集合。该实现可以根据特定的需求进行修改和扩展，比如支持更复杂的图或读取输入数据。欢迎提出进一步的问题或需要额外的功能！
- L) X0 Y1 U9 B2 t# a
$ }7 G/ x: J3 N5 [) u& ~