查看: 3158|回复: 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> ( k' G$ v7 N( y
#include <stdlib.h>
, g4 o7 g& K, t+ p\" @# y
! w* Y* Z& z5 V5 i
#define MAX 100 }1 K4 W5 Q h% D
#define INF 999999 0 V# c5 |; u: M( P g/ z7 k
& S* B# m# i$ t
typedef struct { 1 i% Y) G3 f! d' H( `
int u, v, weight;
2 I! g- n4 I: |$ q+ G! {7 k
} Edge; & m( u7 X% F4 A6 P' o
. {$ k4 x; v3 a: a% Z1 y
// 并查集结构
, v9 ] ]. j; ]) `! r* r9 R
int parent[MAX]; ( I1 j( h) r- L, X, t- A/ `2 [
% Q\" u1 D7 y9 o( Z* x
void init_set(int n) { ) f+ H d. m+ O, g+ x+ B
for (int i = 0; i < n; i++) { + p6 C# E1 C9 T\" z( g7 h5 }
parent[i] = i; + o* G. {! ]; s0 B8 w- \
} ; u& L$ r/ f1 a9 X
}
; r\" a: @' }3 s6 k4 q a
( a) v8 _' M2 v W' I
int find(int u) {
- q- m: \2 e5 c) ` g: T; y! }
if (parent[u] != u) {
2 e/ M# s. z9 j
parent[u] = find(parent[u]); // 路径压缩 / w$ X {# ^- S. c
} * o' V( v/ y\" U; h
return parent[u];
5 F* w) H! o, a: z
}
) S& R- }2 d. J* w9 p
% t7 p4 v5 f7 g/ l+ z
void union_sets(int u, int v) {
' P8 H p# w0 [, [% ?6 S
int root_u = find(u); 8 C\" x( U. {' s+ z6 U% s
int root_v = find(v); 5 @! B- |4 k$ Z2 e9 e
if (root_u != root_v) {
; a) K5 q# ^# M9 d) Z; ]' S3 b8 o! d
parent[root_u] = root_v; // 合并集合 - r) c# [% n\" _2 t
} * B+ Q& V1 b4 U( h% \# g* ?1 e$ [
}
7 M( {1 W y* p; r( K
$ M9 U5 G7 ^, P) e# y3 G
int compare_edges(const void *a, const void *b) { 5 s# f' h% z8 x K( R+ Z
return ((Edge*)a)->weight - ((Edge*)b)->weight;
( x3 ~# A4 b M
} 1 ]+ n4 s) O, }) O; I* a( n' m L
( \0 z' v2 g5 C a9 w
void kruskal(Edge edges[], int edge_count, int vertex_count) { 1 |/ a+ Y+ ?1 |4 V# Y\" `
// 初始化并查集 ^6 h u1 Y0 X$ o
init_set(vertex_count); ! \& k7 u3 o/ c% c7 C
' d3 U; b w ]* c6 F* `, C
// 排序边 4 n7 B3 D1 l, q) T* I% T7 P$ Y
qsort(edges, edge_count, sizeof(Edge), compare_edges); 1 W' ~! Z! L, C7 r& I
: w0 y1 K/ E) P: J6 o, r+ w
printf("Edges in the Minimum Spanning Tree:\n");
6 `! d! ], `% b; a\" H
9 {& }& r/ M7 X. w# [1 z$ o
for (int i = 0; i < edge_count; i++) {
6 f! g( x4 t1 O8 z8 S' {' S
Edge edge = edges[i];
4 \& f% g2 ?5 a4 p: |0 I% l' e
if (find(edge.u) != find(edge.v)) { . e% F k5 @8 H! a4 t h
union_sets(edge.u, edge.v);
+ V. { i0 I7 Z; r) I\" t6 [7 o
printf("%d -- %d == %d\n", edge.u, edge.v, edge.weight);
3 x: q# M: b) P0 j( }. D
} - U, ` E- {9 M0 D; w3 Y
}
6 E! u+ \% ^; o+ n- |3 ?$ t
}
' c, k+ Q( {& Q i
5 E+ N. G# X; f\" R/ g9 x4 G
int main() { : m) Z; ?! @/ @8 g$ q+ e6 g' E
int vertex_count = 4; // 顶点数
G! C7 z' f* b. |' x( O
Edge edges[] = {
; t, P3 ], x! d3 k4 ~
{0, 1, 10}, ( x! U9 l% H' y- U7 L+ d. U
{0, 2, 6}, : h$ `3 m) H3 I4 ]1 o\" j& U
{0, 3, 5},
# M& H# r7 N1 N3 U* }/ e
{1, 3, 15}, 4 `$ S0 B2 T* s, l. o7 ~- t
{2, 3, 4}
: k3 ]1 y! D K2 x! e
};
! V C& S4 o- P% l% q- X0 E
int edge_count = sizeof(edges) / sizeof(edges[0]); E1 x- e; i\" o* F
) M6 }3 y) Z) M% V$ }( y
kruskal(edges, edge_count, vertex_count);
' J) r+ ?( {, Y
5 K' z! O% w$ C1 m+ u; X$ y' o
return 0; 4 \6 b5 g% y. T- H; L! p
}

复制代码

### 解释代码

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

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

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

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

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

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