Kruskal算法C语言中的实现 - 数学建模社区-数学中国

#include <stdio.h>
* q9 E& o J& w; b
#include <stdlib.h> % ?# V: }- k( Z! `
: q& _+ x* B" ~: Q8 O7 B- C
#define MAX 100
7 B, [/ ]! a# W% X# B
#define INF 999999 1 f$ r# r4 n: g, A' U7 C# `
1 J! K% P2 u/ X0 i l/ J6 N
typedef struct { % S' i/ K' L8 E2 q
int u, v, weight; u5 }6 m5 l4 b0 R. L( `1 V
} Edge; 7 P k! d9 b6 r7 n5 h
* @+ L! P4 S7 Y: t4 g! y: J
// 并查集结构 $ t1 E/ ]7 a& f4 w' i$ }$ H
int parent[MAX];
( u" T& k7 \* d
6 a9 T) S( B7 l8 S( z2 {0 ~
void init_set(int n) {
" o* m/ T. D1 g+ S. p
for (int i = 0; i < n; i++) { ) X! m4 a( s9 s$ V% t4 l& \( f
parent[i] = i; 2 S8 e, P3 L0 ]' g3 r5 v5 `
} & Q; ]( d! ~- `
}
" u! g9 t6 d% p0 l1 J4 B+ \# Q2 x7 p1 Y
0 f7 ~ i' d! @, X$ r
int find(int u) {
/ K1 c) i* \6 ]& X
if (parent[u] != u) {
% B- L0 H7 [2 F' C
parent[u] = find(parent[u]); // 路径压缩 ( A0 s8 m, A9 Q3 B/ Q5 K
} 1 E* R% @# f* Y8 K
return parent[u];
2 e% p* f, z R0 O" Z
} , O* Q% E* @7 M4 ~3 R
( H7 p) R% A8 I5 i
void union_sets(int u, int v) {
; `. P+ e5 v/ R# e5 J/ b0 V8 H
int root_u = find(u); ! J; P: \: q' Y
int root_v = find(v);
7 u0 y! F" z/ m+ y C
if (root_u != root_v) { ; ]+ [" Z: d2 o
parent[root_u] = root_v; // 合并集合
! h- f$ G) i W
}
} ( H6 |& A0 }1 m) V# j
4 _8 C- T, b, g" h7 P
int compare_edges(const void *a, const void *b) { * w! ?7 a2 ^: m$ o
return ((Edge*)a)->weight - ((Edge*)b)->weight;
, o7 ?0 Q0 n/ }" v& v8 E, S! e
} ' @' m; k" e4 z+ E
9 L2 E! }! F/ z) H
void kruskal(Edge edges[], int edge_count, int vertex_count) {
3 D' U- I1 X5 `
// 初始化并查集 1 [: E4 i5 o" P2 U
init_set(vertex_count);
8 L5 ~9 W2 J) B( L" q/ r
4 _5 C2 `' U& b$ X/ f. F% n! }
// 排序边
* p/ T4 `+ ]& K! q1 c, s1 \
qsort(edges, edge_count, sizeof(Edge), compare_edges); 4 B2 B: i( @2 w# T3 Y
0 d2 b9 m) J. R [/ F$ _. O
printf("Edges in the Minimum Spanning Tree:\n");
4 S8 D9 C4 D, ~9 h; @
$ a3 n+ P, ]- D: L0 Z& P
for (int i = 0; i < edge_count; i++) {
' V0 J0 }1 g; M) n y
Edge edge = edges[i];
* D' }1 z2 _1 q! p" {: Z: d
if (find(edge.u) != find(edge.v)) {
1 ?% D6 K7 s( S8 O+ t8 Y# V/ s' _
union_sets(edge.u, edge.v); ' E7 l3 m( x, B1 I
printf("%d -- %d == %d\n", edge.u, edge.v, edge.weight); - x/ i& S: e% y, I2 Q
}
8 x' L* B8 H8 D' X4 U+ z9 J) u
} 9 h4 k r. H/ O% n
} V9 y- v7 h( k4 Q0 u$ d
% g$ V8 S& c A3 G, m; C
int main() {
( L* C. i8 N$ S8 \
int vertex_count = 4; // 顶点数 : ]4 C5 R( U. L2 F" p
Edge edges[] = { 5 f8 s+ D% O7 o. G
{0, 1, 10}, ; C p' L3 R+ g) `, x
{0, 2, 6},
* k9 \/ Y6 h) y4 k/ w
{0, 3, 5},
+ b. ~& T. ]6 O: Q% h
{1, 3, 15}, + o* C; X- @7 B; q1 W, M/ D
{2, 3, 4} ) ?5 C# I: S5 [4 B9 r4 v# W! i
}; - v% Q/ ]$ O G: L/ Q6 ]
int edge_count = sizeof(edges) / sizeof(edges[0]); ! l, Y% `/ I! N, z y' Y1 l ^
7 z |* F' _. ?$ l
kruskal(edges, edge_count, vertex_count);
; l2 T5 o0 F- S! [
. l( e4 G! @" _- T5 v8 I9 G, D/ q
return 0; ; }" V, o. ^4 p/ ~
}

复制代码