查看: 2307|回复: 0

Kruskal算法C语言中的实现

字体大小: 正常放大

1177 主题	4 听众	2891 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

### C 语言实现步骤

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

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

### 完整代码示例

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

#include <stdio.h> # A! u2 F0 Y7 S$ U7 t; D& x0 F
#include <stdlib.h>
4 l+ t, h, W/ k2 P
- O' o: Q9 l1 ^+ x2 x i9 [& V
#define MAX 100
# T& f' c% T6 e6 f1 G. I; a2 G& E4 @
#define INF 999999
8 r7 C' O5 a: R# P% i7 w( S
8 h7 \1 F' K5 Q4 Z$ _ T& ^. u
typedef struct { ' F K/ U4 T7 i. H% H) i
int u, v, weight; ( G0 \2 I$ A+ O8 Q% j, d$ t4 q8 u
} Edge; , N. W1 D4 c1 I\" N
+ W; T1 r* W( r& b$ \1 M
// 并查集结构 # h! Q5 U8 y0 v: I( ] ^% C
int parent[MAX]; & {+ W3 H% u/ } X2 q j# Q
9 @) t\" ~- y1 b, C
void init_set(int n) { l7 z; z) |9 A4 w' }
for (int i = 0; i < n; i++) {
8 T& [. Y1 O! E: D
parent[i] = i; + G: S2 _5 f- f+ x3 }( r
} & S1 o7 t1 c4 R' j& ~
}
0 }8 A( Y @- J% A4 K
& w+ i7 w% X( U
int find(int u) { ) b# _: m# `, i9 k( L! B3 ]: P/ T
if (parent[u] != u) {
. V [; L8 [! n) n* C8 |& q& j
parent[u] = find(parent[u]); // 路径压缩
* c/ @+ Q6 S) @* |& [
}
4 H* h3 q- X6 ~& ~+ `! G) T6 q
return parent[u]; ( P( z# f5 B# A& v4 ~+ c/ \ b
} - G6 i( T\" E6 z8 \4 ?5 |) y
5 D0 F) d5 I; g3 I/ ]
void union_sets(int u, int v) {
/ s9 R4 I. L: ^\" j% Z
int root_u = find(u); 0 S+ G6 C# G9 o. e0 r% j2 V, }3 n
int root_v = find(v);
5 Y6 w% y d0 o- D7 I
if (root_u != root_v) {
+ G/ H+ D7 L7 W( r: H, D1 N0 L
parent[root_u] = root_v; // 合并集合 ' C9 w/ W0 q6 [, c# ~2 e; [. T& C
} ( ^& q7 D* X. M: ?
}
! ~) }# c4 r. W; w' Z* \0 o/ b
( x* p+ z7 ]! U' s2 m) ^
int compare_edges(const void *a, const void *b) {
+ u9 b8 {4 l/ `( r* D
return ((Edge*)a)->weight - ((Edge*)b)->weight; 0 t9 d0 i) p) f; ^ z
}
* F* k) n9 y\" A, E$ `1 e
5 H7 P7 D. b# a& }9 e
void kruskal(Edge edges[], int edge_count, int vertex_count) {
/ Q. B5 U. a7 f
// 初始化并查集 & F5 w( K- i' p r& P
init_set(vertex_count); 1 d8 v. @ a- Q6 o: ]: p8 \' u& d
3 b9 [# Z S) {, J
// 排序边 / M7 R\" ^; {6 t, b3 i2 A
qsort(edges, edge_count, sizeof(Edge), compare_edges); 5 G8 e$ N& s+ k1 |% U
, p* Q$ l+ M0 ]( J9 ] E. H$ [
printf("Edges in the Minimum Spanning Tree:\n");
8 Q# K' U8 d0 M
% [6 @, ~7 U& X5 [
for (int i = 0; i < edge_count; i++) {
0 F& U) u) m1 r! W) m% i
Edge edge = edges[i];
0 K' S0 d& ^( ~2 G& n
if (find(edge.u) != find(edge.v)) {
- N1 q5 B+ `. C: o: Y) \
union_sets(edge.u, edge.v);
0 C. `: U# C5 x6 y9 B5 R. p, Q( \\" ^
printf("%d -- %d == %d\n", edge.u, edge.v, edge.weight);
\" k, ] n! M\" d% f& F
} 3 a* v }' b0 {
} - C( \6 T }+ h, [* N2 N& G
} + ^6 W2 f' ^6 J8 `) `) G! ]
7 G t2 D% h3 f1 A! m7 P' C2 L' j
int main() {
1 @) X/ Q9 K! y# B
int vertex_count = 4; // 顶点数
# c7 ~9 y% s% [0 P' k& |
Edge edges[] = { ) B% l! C. p3 x$ h; o- U
{0, 1, 10}, - `. ~) X/ u, B( u: V( g; Z+ d
{0, 2, 6},
& q7 P- S5 d5 n$ H W
{0, 3, 5}, 9 _2 w9 V3 ?/ x\" d6 O: j
{1, 3, 15},
1 E/ m; u# x$ b
{2, 3, 4} 0 W4 |! w+ n: G9 z9 ?
};
a- e\" o3 p\" Z K J% Q$ [
int edge_count = sizeof(edges) / sizeof(edges[0]); 4 K& Z& e\" Q7 Y
8 B3 z$ y) } I- B T; s
kruskal(edges, edge_count, vertex_count); # a5 B5 U& c( c. \
' C8 O, s5 U) K, b: H* g1 l( S
return 0; }0 f* O+ P5 z$ B! Q
}

复制代码

### 解释代码

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

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

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

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

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

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