查看: 3156|回复: 0

Kruskal算法C语言中的实现

字体大小: 正常放大

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

发表于 2024-12-12 15:00 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

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

### C 语言实现步骤

1. **数据结构**：
- **边（Edge）**：表示图的边，包括两个顶点和边的权重。
- **并查集（Union-Find）**：用于管理和合并不同的集合，以检测循环。

2. **算法步骤**：
- 将图中的所有边按照权重进行排序。
- 使用并查集逐边检查，如果两个顶点不属于同一集合，则将这条边加入最小生成树中。

### 完整代码示例

以下是 Kruskal 算法的 C 语言实现，包括必要的函数和并查集的实现：

#include <stdio.h>
1 g4 N) h5 B8 A9 R: G( A4 q
#include <stdlib.h>
: W; K) W+ z1 g1 z, A D\" ?: ^
, C1 X3 o0 P) w- I: P U( _6 }$ q5 P
#define MAX 100 ' q* k/ v6 E5 z& u& d! g6 t
#define INF 999999 9 Q; t. `* ]$ v8 ?% _9 [, h
! ]* _7 M2 m# e3 A\" }% V
typedef struct {
3 H3 k1 S& x/ |1 r6 c& Y. D
int u, v, weight;
& C2 ~% A/ F2 F6 I' ]
} Edge; 4 i+ O( Y\" c) Z3 f9 p. f
4 v/ ~: ?; f0 l0 q
// 并查集结构
+ J; g3 H, r& F8 m& S; @) y
int parent[MAX];
1 H2 T' t\" o- s4 U. [
3 F. G9 L3 K& `# a$ O
void init_set(int n) {
$ _9 ?! z, x5 D; v K- d
for (int i = 0; i < n; i++) { 3 R! ~7 H p& g, O8 Z/ H
parent[i] = i; 8 }1 V! z$ ?2 }2 b, F
}
+ i* g\" O3 P; T# Q
}
0 H+ l1 ~/ r2 i\" d6 h; t4 T Q
3 W/ O% t% q! a
int find(int u) {
4 Q1 {8 K% f, m* d* ]! r( a) V
if (parent[u] != u) {
. \ r' ]0 m3 b: s% a\" x$ @
parent[u] = find(parent[u]); // 路径压缩
! ]5 ]- v0 w B( L
}
5 w) A' x* h1 y2 l0 V8 p6 p; f
return parent[u]; 4 F; l' v4 a# J; o p+ ~
} l- r0 S6 a6 E# M/ f
+ B# x) F) z2 J( |
void union_sets(int u, int v) {
* a) m' s. c) K& N4 D0 ?$ W7 z
int root_u = find(u);
/ S% O+ `% z) e; W7 Y4 N. m
int root_v = find(v); 5 ]6 x$ N\" E2 e9 e ]8 m
if (root_u != root_v) {
# W8 ]4 b( F$ |; H8 E1 v! A9 O
parent[root_u] = root_v; // 合并集合 4 p. t, Y K7 f. {7 X& h$ a; a+ `
} 1 C% x7 ^# S( I
} & }( b# q2 i! o! T7 y- _# t
2 l, ?7 q/ S) x* E6 w# z
int compare_edges(const void *a, const void *b) { 3 f4 r6 h4 ^# f4 c7 `4 U/ r
return ((Edge*)a)->weight - ((Edge*)b)->weight;
% `* _$ X' J\" I! _, r7 m
} ; D5 W6 U- ~ c0 V& F; h
) H8 H, Y# V& m- o1 e
void kruskal(Edge edges[], int edge_count, int vertex_count) {
# |$ I- M% p, U- t
// 初始化并查集 ! l$ _$ e\" D4 O
init_set(vertex_count);
. S! e+ N2 N' h
( I! Z\" P( E% t3 `- ^
// 排序边 ; K3 E' T, {3 Y7 I
qsort(edges, edge_count, sizeof(Edge), compare_edges);
|6 _9 h% C6 O8 w. E, ?% b
$ R- G\" q* q6 D; f8 a, F) [3 W% S
printf("Edges in the Minimum Spanning Tree:\n"); 0 e: h& _/ Z0 P, m+ x7 c
) R; a% O) M\" h; r X
for (int i = 0; i < edge_count; i++) {
4 ?$ V. b& E8 H\" x7 I6 r5 Q% l, g
Edge edge = edges[i]; 9 D\" l4 A' y# D, K: V1 l
if (find(edge.u) != find(edge.v)) { ' `# V3 w\" L6 ]) L
union_sets(edge.u, edge.v); 1 b: h1 O3 h\" s' N
printf("%d -- %d == %d\n", edge.u, edge.v, edge.weight); \" u3 P! c8 q4 C( Y0 \% w. k
} / C+ C/ `% d' S' a- S
} ; Z' Y! f+ i\" B( w6 i0 ]
}
- `. x\" `' _ K
6 q8 a1 @0 J) u( K6 r' y! P
int main() {
6 p7 X. A: |, p3 r\" W# @& V
int vertex_count = 4; // 顶点数
2 f0 H$ r/ z$ H- s5 |% J' Z1 x% O) e
Edge edges[] = {
2 ^/ ?) b\" W n4 `! |# \
{0, 1, 10},
6 u' c5 F- |& Y! \4 V' i
{0, 2, 6},
\" _$ D: W5 W# d; t# G4 A
{0, 3, 5}, ' [) H1 p8 l( k {& _ e
{1, 3, 15},
9 Y& R2 L& i. Z2 \2 G0 ?( B
{2, 3, 4}
+ |1 m& P0 L; }; r+ f1 P
};
8 ?- ]+ b$ d6 O) d5 Y, g
int edge_count = sizeof(edges) / sizeof(edges[0]);
6 f) `; N, ^) }9 e
7 L! d0 h8 H! v' a- U: ?
kruskal(edges, edge_count, vertex_count);
* h4 W6 m P* s$ h) I+ J
; }+ o4 [2 _- w8 N
return 0;
# N; h- k, I5 K
}

复制代码

### 解释代码

1. **数据结构**：
- `Edge` 结构表示图的边，包含两个顶点和边的权重。

2. **并查集操作**：
- `init_set`：初始化并查集，将每个顶点的父节点指向自身。
- `find`：查找某个顶点的根节点，并进行路径压缩。
- `union_sets`：合并两个集合。

3. **Kruskal 算法**：
- `kruskal` 函数首先初始化并查集，然后对边进行排序。对于每条边，检查其两个顶点是否在同一集合中，若不在，则将其加入最小生成树。

4. **主函数**：
- 创建一个简单的图，调用 `kruskal` 函数并输出最小生成树的边。

### 注意事项
- 确保在编译过程中链接标准库，适用于小型图。
- `main` 函数中的图是手动定义的，对于大型图，通常会从输入或文件读取数据。

### 总结
Kruskal 算法实现的关键在于有效地使用并查集来管理图中的集合。该实现可以根据特定的需求进行修改和扩展，比如支持更复杂的图或读取输入数据。欢迎提出进一步的问题或需要额外的功能！