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

#include <stdio.h> 6 W# |- \. S& ^# G6 S7 m/ V! W5 @
#include <stdlib.h> * U& m" k* g1 c8 }! O! f2 Q1 e* m
2 P9 D% C0 M/ D% [8 q: N* h1 ~. E
#define MAX 100 9 p& `, {( Y u' N. a
#define INF 999999
0 e) h `% d1 N
* t! D5 p* h% b0 \9 d9 p9 b- B
typedef struct {
- \- l" E; |0 y. N+ h! d9 J
int u, v, weight; 0 ~2 z+ T7 D b+ h- m9 i
} Edge; 5 h/ d P9 T7 L W) g) M& R4 |
8 q7 t4 Z$ `0 A4 M
// 并查集结构 ' s$ z$ u6 o, W/ f2 W* Y7 Z
int parent[MAX]; 4 f, u0 ]! b( e3 h$ l+ A
3 l% a% Z/ `! `$ _/ h" x' K& v
void init_set(int n) {
. x9 \ Z1 b' @
for (int i = 0; i < n; i++) {
$ S4 r" T- c! Y* s* R& N% b$ D
parent[i] = i; 8 F7 X' q0 r0 I/ y1 P
} ) i2 j8 u+ p) s: ?/ d
}
$ @! v; K6 u; n9 K) F% g P
. x- F! B* `9 @+ L7 \
int find(int u) {
9 k- {$ ^5 u9 K, s# y( O' D t
if (parent[u] != u) { 2 w: B6 W/ I& U' {1 E- a
parent[u] = find(parent[u]); // 路径压缩 $ p9 N5 j. p1 r! [1 ]) B2 P
}
" f" X" |7 O7 {+ x# m; `
return parent[u];
5 v, w+ C" n0 M3 }1 f. e
}
! T8 I& \+ e5 d' M. Y' _, B. B! j* \
+ u& X1 h& P8 T
void union_sets(int u, int v) {
T9 q$ w1 `! F4 N& j( N/ L7 |, ?
int root_u = find(u);
8 w5 r2 Z7 w1 O6 s& G7 F" z
int root_v = find(v); 6 _* j3 W4 z' y+ z3 o4 R4 b
if (root_u != root_v) {
; p' C) T( }" b7 c1 X+ H# M
parent[root_u] = root_v; // 合并集合 & S e! Q5 f1 P) t2 c
} 4 |; v+ U9 ~* L7 c3 P
} . a9 }) ^8 F2 i' x3 e% R
( l' a, R+ r% Q8 R4 Z6 {* w$ c$ O/ U6 x
int compare_edges(const void *a, const void *b) { . r" p# }- Y. }
return ((Edge*)a)->weight - ((Edge*)b)->weight; 5 l) m, L8 t$ @+ E8 H
}
# g6 V- ~8 o! `! Q# I7 R9 t
+ C/ X; E M- t6 Q
void kruskal(Edge edges[], int edge_count, int vertex_count) { - G3 b9 C; k0 y' l7 H
// 初始化并查集
* R" D$ j5 E/ C" v3 J: u' i
init_set(vertex_count);
% w3 G8 g$ t9 T4 {+ T9 y l Q
# l" [8 o& g* U, \' _' ?. D) s- t
// 排序边 7 q! O1 a5 U5 z! n( M% }! A
qsort(edges, edge_count, sizeof(Edge), compare_edges); - c" {$ U5 j9 d
- b# W4 j Q7 P, b4 h
printf("Edges in the Minimum Spanning Tree:\n"); / [% B" w$ R1 E* r0 @- E/ d( ?
( R. n- a: k' R) Y6 r
for (int i = 0; i < edge_count; i++) { % g9 v: o, `: t, q3 U
Edge edge = edges[i]; 6 r7 M) R( S1 h! S8 X4 i
if (find(edge.u) != find(edge.v)) {
2 ~6 M7 B- A9 c' _
union_sets(edge.u, edge.v); " L( c; z3 B; ?4 K
printf("%d -- %d == %d\n", edge.u, edge.v, edge.weight);
1 k7 M2 `/ v2 P" d4 U2 e' M
}
3 G$ V# \7 ?4 c0 X! S1 n
} - m% E" H. W$ C) l- D2 t; U8 e
} 0 j$ D) \( f% m1 R# [$ {0 t$ ?; p
" x* N( h, j, c4 V; r
int main() {
I: O; B) L# q: n( j2 T- N' ~: ]' \
int vertex_count = 4; // 顶点数
* ?- e$ b X- C5 ~, k9 X
Edge edges[] = {
7 u3 j( n, J2 W4 Y- r q& v: ^
{0, 1, 10},
* d; ^% Q, e5 `1 N% I; V
{0, 2, 6}, m8 L( y \ B; v
{0, 3, 5},
! S7 l" \+ t: ~; y* l4 g
{1, 3, 15},
2 u/ P# _& x0 @. H, _- }
{2, 3, 4}
( t3 Q0 H+ j" {7 M9 A- V
}; 5 H( ]( \6 B$ k8 b
int edge_count = sizeof(edges) / sizeof(edges[0]);
8 |6 C: m& O* O- b* @& J; m8 t
: }. F8 c0 v- C" L
kruskal(edges, edge_count, vertex_count);
- s7 W3 g2 S' h* a' X7 n0 d+ f- I
) `7 j2 e+ p2 g& e
return 0;
, \) r6 R% I5 w( H
}

复制代码