查看: 3116|回复: 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> 5 R5 `; x$ W\" D' ~5 c
#include <stdlib.h>
& @+ Z K+ Z- J# v
7 q\" Y) y8 P ~2 }2 a0 I/ V
#define MAX 100 5 i$ w% t: B; G9 f7 u
#define INF 999999
6 {4 J; r6 r2 f2 b& g1 r3 y
. [$ M1 w$ e1 K4 r- j
typedef struct {
+ C e4 q' H) j- g: W+ f) \
int u, v, weight; 8 U% a! z4 c* j8 Z
} Edge; : }/ }+ O8 f' B! z* ~) N
, H4 ~6 S0 x$ F/ [ u
// 并查集结构 6 W; e0 n# i Z' w2 e; \
int parent[MAX]; \" p- z; A; G; r0 U
' O) V7 I2 g3 P: z/ h! c; h
void init_set(int n) {
5 L- ?1 K4 z4 @5 C1 Z
for (int i = 0; i < n; i++) {
: M: u J. R/ ~- N$ h: p
parent[i] = i; ) w# B3 n) j9 i# ]; B, h+ r: B
}
@. B2 C2 H& u4 k2 i# j1 F
}
1 u' @! R U- ]$ \
& H+ N3 B7 ^3 b) [- l9 T
int find(int u) { # x4 W1 K- w! H\" M/ Y& |
if (parent[u] != u) {
4 R N4 f, R( D# T$ P
parent[u] = find(parent[u]); // 路径压缩 8 H' ]$ s, @8 l! o5 T
}
1 A- A& J+ N/ x v7 h8 G
return parent[u];
) S% @% d3 w$ \* j8 j
} % F) w, l, [* B: K\" m
0 ^$ l. Y- Q* D+ _1 V* w2 |
void union_sets(int u, int v) { 7 U; U B3 _- B2 @
int root_u = find(u); ! C7 i2 A' z( S( _% C' K3 _3 W
int root_v = find(v); 5 I, `5 g5 n' c( [# d
if (root_u != root_v) { : ]& A, ]( a% z
parent[root_u] = root_v; // 合并集合
* |( V9 G3 h; t, E f! U
}
) {+ A% X* T* y h( S7 \. i
}
* D1 k0 m& k3 v\" n8 R1 H
* |4 o; j. s1 {. I2 I$ a5 d3 @$ J; B2 E
int compare_edges(const void *a, const void *b) { # k& n# [+ l5 o\" G4 E
return ((Edge*)a)->weight - ((Edge*)b)->weight;
# v5 b, V: q Q\" G: ?$ |
}
* p; K. W/ C4 G2 R; ?! n
/ V: A( h+ ~0 o
void kruskal(Edge edges[], int edge_count, int vertex_count) {
# k. j+ w7 y! r: M+ V! t# k2 j2 J
// 初始化并查集
, I( b( L B+ a- w
init_set(vertex_count); # |9 j, F; R& @6 t' k- Z
, S- E! T+ g, S2 a5 H+ F/ T
// 排序边 8 L4 y6 j' k+ W# s; m
qsort(edges, edge_count, sizeof(Edge), compare_edges);
& _( t8 n0 e9 e/ U4 |
+ R( M9 |: H9 t T
printf("Edges in the Minimum Spanning Tree:\n");
) d/ S0 p' Z) R2 y
3 `0 w# H0 f# \5 R7 p }0 `
for (int i = 0; i < edge_count; i++) {
3 `\" z8 [2 T& b0 U! Z
Edge edge = edges[i]; 2 A0 ^+ C/ ?% U% U( w) g# ^
if (find(edge.u) != find(edge.v)) { 1 h( Z8 A; u& d9 W' m
union_sets(edge.u, edge.v); $ [7 o6 ~: z) ^9 D( p
printf("%d -- %d == %d\n", edge.u, edge.v, edge.weight); * K2 Q5 r\" F9 ~& I; P( ^9 _/ v
}
0 m0 n. a2 j( ^2 z
}
$ [3 Y! a5 K! n. h' i0 E. t
} 9 E5 {\" @9 H+ \/ e
7 P+ A* a3 k. D# {9 S% j0 v) U7 ?
int main() { ; X% Z- F$ a; ]$ O% Z/ K\" Y( T' Z
int vertex_count = 4; // 顶点数
$ p\" h/ h l, _\" M) ]% J. C% z _
Edge edges[] = {
7 _7 w( h) G+ h
{0, 1, 10}, - \- @. u2 X( [) E
{0, 2, 6}, % d: i: C$ N \6 |: m
{0, 3, 5}, 4 q) i$ ?8 m/ K. n
{1, 3, 15},
( v# g* n0 T2 x
{2, 3, 4} c' v+ ^& {- E. t9 H. k
};
% |- f9 V5 n( t% u# X7 g/ a z+ \
int edge_count = sizeof(edges) / sizeof(edges[0]); , R7 U* S( f2 N
0 n& B. b3 [9 n
kruskal(edges, edge_count, vertex_count);
$ |7 f0 S9 J, @
3 q+ b% F1 E3 C5 M
return 0;
\" v6 H+ J\" t8 v m8 C/ u
}

复制代码

### 解释代码

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

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

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

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

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

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