查看: 3140|回复: 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 i5 B, f* W* x1 u
#include <stdlib.h> ' u. m: q _1 ]1 U
h$ |1 J\" U+ t. \- O& B( p
#define MAX 100 4 ]& b! |; ^; {+ F, u: U) @) A
#define INF 999999
% ^+ P. X# t$ r0 w% X7 k* H' z
- t: m* Z\" L7 M3 U
typedef struct { 1 H$ V5 R2 Q* Y& a- e1 l0 h
int u, v, weight;
9 u2 t* d. D\" b1 q: f i5 R
} Edge; 3 o5 V7 e. h5 D+ J: `
9 e\" X) X* Q1 C# `8 Z
// 并查集结构
7 ?0 q8 x6 f& j8 P
int parent[MAX]; . Z! O5 d! Z5 g
4 s' F& T& ~* k. R: m0 @
void init_set(int n) { \" d9 ]+ G& R2 {; `+ t
for (int i = 0; i < n; i++) { \" F# z+ j0 b9 c6 A* w
parent[i] = i; 1 H/ |; s& ~& T! W/ c
}
3 t& _- \2 [\" Y; f9 g
} - W& T! X* l' W2 k. `
I% U7 S& Q/ j, Q
int find(int u) {
; }: P$ _$ M* V6 O4 B) p2 [
if (parent[u] != u) { : n- h4 u\" A$ k# S9 w9 z7 F
parent[u] = find(parent[u]); // 路径压缩
+ V9 d. p9 g3 q\" N% V, h& d3 K* I
}
( E! F$ ~9 \) w. b! ?) Y/ W. o
return parent[u];
n l+ Y4 Q4 Y\" y, y
} 2 O& p! ~' `4 v. H\" }3 \- ~. o# b& _+ o
\& K1 }2 s0 Q) [. P\" ]
void union_sets(int u, int v) { $ H9 a& m$ P) p2 s
int root_u = find(u); 4 z. S1 z\" ~) w0 r( K: Z. G) s% G
int root_v = find(v);
7 F* u' ?+ D, F p+ u
if (root_u != root_v) { % | t2 j/ l' e8 x- h; g5 M
parent[root_u] = root_v; // 合并集合
0 {# ? `9 {5 _# `9 C( D
}
) G3 g& s9 Q& R
}
! `% J2 r% A% _
K4 l1 z( \* M# K4 U' ]7 L
int compare_edges(const void *a, const void *b) { R8 x2 ]* z0 W' ~\" P9 i8 u
return ((Edge*)a)->weight - ((Edge*)b)->weight; - t3 r7 I4 V. L\" J0 H; \
}
8 O2 |2 I& w7 m$ u, M, O) A
( {' A7 x8 q* m5 D. Y1 @6 N
void kruskal(Edge edges[], int edge_count, int vertex_count) {
/ Y$ ]6 g2 k; ^( \- V/ A. i
// 初始化并查集 \, n' k8 C8 E
init_set(vertex_count); # f& K( k3 D8 R4 x0 T
# s1 k/ Y- Y* C: x. l$ F\" R! O
// 排序边
- L2 |& x) k$ r0 n
qsort(edges, edge_count, sizeof(Edge), compare_edges);
3 T: F$ K5 t7 E4 h, Z
; j* g& f: W' ]8 L. o! _( F
printf("Edges in the Minimum Spanning Tree:\n"); ; I+ M! @; i3 [: x' {
3 m& i+ G+ `8 `& k. e. x
for (int i = 0; i < edge_count; i++) { ' d' c) Z7 p* n; E6 ]- ]
Edge edge = edges[i];
7 ~2 z: C; u. B- F4 a+ ?# G
if (find(edge.u) != find(edge.v)) {
1 S# _6 s2 E: p% i* U
union_sets(edge.u, edge.v); 1 t% r% w\" R0 n! x
printf("%d -- %d == %d\n", edge.u, edge.v, edge.weight);
5 A3 b- y# A- g; `* t9 e
} / \) ~/ P: h. F7 d* G- M
}
9 Y\" [/ S1 O4 n5 f
}
, H$ b5 \( u& W) ?4 u2 a
\" P) Q, W( f/ y7 A& {
int main() {
' S# I) {: i2 h5 ]1 r\" Y2 y
int vertex_count = 4; // 顶点数
3 _4 j\" B* T9 X4 q( g
Edge edges[] = {
W& i- s\" l. s: s( O
{0, 1, 10},
) `+ f( O; L0 |5 o) F
{0, 2, 6}, + n& ]' ?1 P. z) Y( |# r
{0, 3, 5},
6 Z& g# Y# c2 } n+ N
{1, 3, 15},
# v5 s' @0 t; X& a! k& K
{2, 3, 4} % {3 ]% B; ?$ s% B0 e. \
};
$ k# K8 s5 {: P& q% _9 F4 `
int edge_count = sizeof(edges) / sizeof(edges[0]); 7 g\" o* L2 U: \9 K, r
& y\" w' _: [' Z* f5 A6 D
kruskal(edges, edge_count, vertex_count); 3 ]6 [5 K) i* Q& l' S
8 g1 {% q0 S$ s3 L# M% P
return 0;
$ a( x) D\" H$ Z- r
}

复制代码

### 解释代码

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

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

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

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

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

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