查看: 3160|回复: 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> |8 K7 h2 Q8 H
#include <stdlib.h>
, _3 ~8 r8 Y9 }, | Q
1 e5 \! i$ f' l5 L* t: q6 b/ G. x
#define MAX 100
9 s0 y( Q& Q1 f6 i# s
#define INF 999999 $ u6 B( a+ k& y4 z- A: S }
0 |- m3 x6 B4 u0 E, B8 K\" o9 y
typedef struct {
$ @4 B! y! D7 D8 M {: H7 A
int u, v, weight;
3 f+ C2 {3 a- s5 k8 \1 o
} Edge; |6 d# a' S: d* V( { l u
, `\" b4 G; E. t, s\" d' [
// 并查集结构 4 A) Z8 z8 R) f\" \
int parent[MAX];
- G3 h6 G/ @/ _
; l\" W9 w. y' V, X( T
void init_set(int n) {
% K) n0 R J4 ?3 Z& O
for (int i = 0; i < n; i++) { * Z- @) q- u1 g& c& o
parent[i] = i; 9 Z1 x0 `2 L1 i$ b6 a+ ?
}
$ e1 y% s$ O7 F, v f
}
]# n, s* I# B* A7 t% S
W. |9 s1 w/ s/ t1 V$ M
int find(int u) {
+ T z; T2 ~ r0 l\" W' a: o9 v- I
if (parent[u] != u) {
& G( R ?2 V; x2 e
parent[u] = find(parent[u]); // 路径压缩 8 W, ?\" W5 j) d! }
} 4 b0 m7 d% a' A) G6 Q
return parent[u]; 2 L% A6 h7 L5 w' {; o! {
}
1 Q' @! t( i, w9 W\" Y
( _6 g0 T9 X2 P' d: {7 O2 g! F
void union_sets(int u, int v) {
+ M% U7 H, J \
int root_u = find(u);
# P* J2 c! Z- l& D4 q, [; y
int root_v = find(v);
7 c, P$ B# E\" x6 O- r( B
if (root_u != root_v) {
) x- x; _% f\" M2 a
parent[root_u] = root_v; // 合并集合 , I/ m/ o* X; t w/ T8 G+ ?
}
5 _' N; S1 A5 t0 V: y/ Y7 h
} 6 ~1 P! X, G& m/ p, ?& S; {
$ r. ~! ]9 {. R# u$ Q5 J# ]
int compare_edges(const void *a, const void *b) { * I1 @& a* |1 Y V3 Y8 [2 F
return ((Edge*)a)->weight - ((Edge*)b)->weight; # |) T. C5 D- r6 Q4 s, @, k
}
) Q1 c, n: [/ {
% H/ {$ e, v/ O\" v# \* H% ] @
void kruskal(Edge edges[], int edge_count, int vertex_count) {
. s0 x2 ]# {+ s; K9 Q, w1 Y
// 初始化并查集
) \& { C# ` ]7 V
init_set(vertex_count); 3 O% p. l$ [: V# K- ]
! r- y, E. p; h9 I9 o( i: o
// 排序边
: F! f. F+ a' ]6 j/ s7 W8 ?: U
qsort(edges, edge_count, sizeof(Edge), compare_edges); . [! a: O' n6 Q1 U2 x# F, p
) u9 N5 m. C& ?* z4 [* K
printf("Edges in the Minimum Spanning Tree:\n"); 8 ]4 n% t. J- g
, n; h2 D\" W. _! M4 c4 ?
for (int i = 0; i < edge_count; i++) {
% l# Q: [! Q# f1 E5 s6 \
Edge edge = edges[i];
4 t\" B0 I* T4 o5 V+ o
if (find(edge.u) != find(edge.v)) {
# V/ B. R: N8 F5 g1 g) }
union_sets(edge.u, edge.v);
, }; P* C2 `; i3 E* z\" n8 W
printf("%d -- %d == %d\n", edge.u, edge.v, edge.weight); 5 e! x+ u: |0 H8 G& C+ m
} 1 a- `* ]4 x- O) h2 ?) j. i8 W4 T
} ' Q8 A( w( P; k; _' j6 m3 E
} 5 H9 q* \! p7 r- X# b/ ^' s
9 ~; i! x; Y\" I# z* c! Y# v
int main() { 3 x9 L6 J$ e: Z
int vertex_count = 4; // 顶点数 3 U! _: T\" Y6 S6 ^2 @ G4 b
Edge edges[] = { / r4 ]3 I; z# d: u. l3 N
{0, 1, 10},
: m% K7 w) A) @\" Q7 n2 G# K2 [2 e
{0, 2, 6}, 4 a7 w3 T\" q9 m! P3 h- T- C
{0, 3, 5}, ; Y) B- E5 k) a8 B3 H* R\" a7 t' ~8 D\" C
{1, 3, 15},
\" k$ R\" t4 C8 G0 c% e' A1 x+ [7 x
{2, 3, 4} # n; Q! P; D b% ?! W9 y
}; # O$ \! W* v) {- c) p0 P\" O$ Y `
int edge_count = sizeof(edges) / sizeof(edges[0]); & ^2 T& R) ~% |8 T) J
( Z3 |2 E; @+ i* a
kruskal(edges, edge_count, vertex_count); ; H9 }4 s e+ f% N, x. [ K; L& z
5 ]5 a* Y' ?8 T- g. _1 P: a
return 0; 2 J5 @, d0 }) ?; w$ H' B7 t4 j4 E
}

复制代码

### 解释代码

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

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

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

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

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

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