查看: 3114|回复: 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> $ _9 a6 i* Y- `6 _; q7 r0 ]* t
#include <stdlib.h>
* L1 {* e2 j5 \3 K: F
5 Q O. I# f, L& a+ H5 |
#define MAX 100 $ J( ]) W t7 Y5 ]7 k9 j
#define INF 999999
5 L: n2 R1 [. z3 k7 O
! u: r3 ^- M5 b
typedef struct {
* Y, q- {- P. t
int u, v, weight;
\" B; d6 a1 L: @0 T' k0 d6 W
} Edge;
0 {, c+ I( u1 @+ U/ p1 D
6 i0 F2 u% {2 R
// 并查集结构
5 \0 L7 l8 A/ S, Y: B
int parent[MAX];
7 ]2 K8 R) i' w$ y
2 L7 \2 `8 b v8 _
void init_set(int n) { ' V/ J; r1 i2 ~, M\" w' `1 B
for (int i = 0; i < n; i++) {
- ?- c7 `5 G2 `+ d, Z1 m
parent[i] = i;
# B3 K4 ~% H0 k4 \6 |\" P& @
}
( G n+ m3 j+ f. _
}
- ~; m% v8 w6 J; ~! ]5 p% w1 J
5 j4 S4 q5 }. @1 ^
int find(int u) { . r4 ^# c\" ]: F5 B, [: g
if (parent[u] != u) { - _9 a3 \. T' p0 A' x
parent[u] = find(parent[u]); // 路径压缩 _: U& x6 e6 U
} - G% w2 _5 x7 [
return parent[u]; 7 N! M6 e; A\" t5 N% O# Y. `2 l
} ! p, D; `# b3 J* _+ r2 b
: {8 t. y% Y1 P& y6 s6 X
void union_sets(int u, int v) {
[$ s6 x- s4 d( S1 ^- V
int root_u = find(u); ; n/ q4 ~* {: m4 h% R i9 Q
int root_v = find(v);
]0 L. g, f; m0 p- t\" O2 J
if (root_u != root_v) {
8 j) ~& x3 B! o! Q& q( T! o* W7 j
parent[root_u] = root_v; // 合并集合
* X X$ T& [3 k1 u
} ; o, b/ k. C: S/ M a: R
} # v( v6 t3 L( q# x
\" ? ?/ @' L6 W+ Y
int compare_edges(const void *a, const void *b) {
7 e9 N, k7 p8 X5 R$ u- l
return ((Edge*)a)->weight - ((Edge*)b)->weight; & ^9 ]! n; x6 `
} 0 `\" q) m: |, a0 j9 [
; Y1 r3 u3 x0 Q, p
void kruskal(Edge edges[], int edge_count, int vertex_count) {
5 T' y! j& d$ E\" I4 V! W
// 初始化并查集 6 t$ r! d7 }, |- O% g9 }# r0 J
init_set(vertex_count); 2 _) c' C9 |! h. c6 A* b! U$ c( o
2 e* ~% m& R8 v, g: V# P4 r/ L
// 排序边
$ ^0 k6 t/ S ^
qsort(edges, edge_count, sizeof(Edge), compare_edges);
' T- i! w( m( {# I8 Q: S0 q n
# I7 T- q5 B0 `3 S# f3 @& z
printf("Edges in the Minimum Spanning Tree:\n");
7 u! T. C8 A4 R3 w; ^% o( X
. W! ^5 s5 L0 H
for (int i = 0; i < edge_count; i++) { ; [+ \5 Z$ ]0 b% o8 {4 A$ e
Edge edge = edges[i];
$ d# q9 @# [# Z7 V0 G
if (find(edge.u) != find(edge.v)) { 5 v; Z. c9 G+ u\" N6 a0 @/ o
union_sets(edge.u, edge.v);
7 P I4 M0 O1 L0 K9 G( I8 T
printf("%d -- %d == %d\n", edge.u, edge.v, edge.weight); ! R, a1 e* ]! L8 ~
} 5 ~\" e/ ~# {9 y6 L3 Y
}
$ z* D) G! |; J, E
} - u# v3 L) [: x! G1 |& a5 z! |
' [* o% }& M2 A6 W$ t; d M9 J! m
int main() {
6 w\" V' h. w, H$ y9 H4 l
int vertex_count = 4; // 顶点数 . W2 o: O, Y% @. ?\" l1 K
Edge edges[] = {
1 e9 i6 i$ R3 X\" l* ~. p) D# G
{0, 1, 10},
0 p$ t2 Z2 \) \$ }0 e
{0, 2, 6},
$ {' j5 y\" D( ]7 R/ }/ J, [
{0, 3, 5}, ( o# t( R: O' G4 f: U- ~+ X
{1, 3, 15}, 4 b4 t$ _7 Y8 e. ~; \
{2, 3, 4}
. S p: u6 R& s' u
};
* ~- }+ B5 p O& R7 _
int edge_count = sizeof(edges) / sizeof(edges[0]);
\" g: q x. c& `) a. U0 V' c
7 X7 T% }7 j! n\" Z8 K' }# g
kruskal(edges, edge_count, vertex_count);
4 L, z! i: d1 P: G0 F
( k! F2 J: p! s0 }
return 0; 0 U. B \/ X J/ t1 G% d7 m
}

复制代码

### 解释代码

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

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

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

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

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

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