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

#include <stdio.h>
3 T! {, r7 v5 t2 x a6 x1 B+ q: n
#include <stdlib.h>
, ^% X P- t9 X
* e7 ^+ k2 y% m& c3 C; `1 V
#define MAX 100 , `# a9 c" v* K. n: X' G- n
#define INF 999999
, R" y% i3 J. ?9 B2 p' R8 Z
% Y, O5 Y$ j3 z5 I Z
typedef struct {
K4 E) D! F; U. V, x
int u, v, weight; & x* B0 N, R$ x2 c- a
} Edge;
4 C0 G. D" s6 t1 U; D
5 R; \! Q8 \7 r4 q0 Q; Q) z
// 并查集结构 % J# V% J' g; T) Z
int parent[MAX];
* c- p1 O* x5 j0 u
# y4 I/ X9 L) j8 G
void init_set(int n) {
- } L# I$ Y0 |- n, K- y5 F$ y
for (int i = 0; i < n; i++) { H! N. e' [! v5 W; a
parent[i] = i; & E7 j0 p5 a: f6 o! I
} s2 S5 Q$ c# @" Y( m4 h C+ Y) Y
}
& A0 v4 }% L6 n; K9 M, F$ l* h
_1 R* |% [& v/ l
int find(int u) {
4 F. C- t1 H9 X2 f
if (parent[u] != u) { 2 D8 E& P9 A* ?. x
parent[u] = find(parent[u]); // 路径压缩 9 @7 w: g4 s! y+ D
}
# y- ~. a3 ?5 j5 y! ]$ {7 k$ c
return parent[u]; + N* A1 G% b, G' J. P
} ' i$ s8 H8 _9 t* O9 D# Q
) ]1 c' b, X. J9 E0 ]4 t$ S% q
void union_sets(int u, int v) {
, e" J; Y' f% V# T0 c4 t/ G# P
int root_u = find(u); e) D5 t1 K+ ` J
int root_v = find(v); , S" I8 x* g J2 E* `9 o
if (root_u != root_v) { , }3 S' |9 T+ C, M
parent[root_u] = root_v; // 合并集合 1 d! n4 Q7 D, B8 Y8 j. A
} 3 _9 E3 U, {" }$ p2 Z) l
} ( b. z9 |- z) w! ^
" L9 [ U" A* j8 l" R: a" |
int compare_edges(const void *a, const void *b) { + T9 L7 t% W7 |
return ((Edge*)a)->weight - ((Edge*)b)->weight; ; c P* J( |/ ]' R% g4 L
} ( T+ D( q5 z) H: g z
' D2 ~. k7 B( x; X/ a0 [% _
void kruskal(Edge edges[], int edge_count, int vertex_count) { * T, e. v% g4 u8 t" S* Z$ b/ h, M
// 初始化并查集 & G( ?1 O" c* D' R0 E# e+ q$ T
init_set(vertex_count); # `5 X9 w* G7 O7 C
0 d+ {6 ^2 }; m, C0 E- O) `
// 排序边
+ D3 F4 ?# T: R" z3 W
qsort(edges, edge_count, sizeof(Edge), compare_edges);
8 y% n* M, h2 {5 s
; S; ?6 s8 D7 X" y6 o9 H
printf("Edges in the Minimum Spanning Tree:\n"); / J+ A |8 ~: A
{2 b, ]1 Y" x) u! J
for (int i = 0; i < edge_count; i++) { , }0 Q$ | A- U, n# a: P# k, f
Edge edge = edges[i];
- t l$ I% b$ W8 r
if (find(edge.u) != find(edge.v)) {
0 k9 r5 C. _. P# {7 D; z
union_sets(edge.u, edge.v);
. M' w$ W, q; l. v# _
printf("%d -- %d == %d\n", edge.u, edge.v, edge.weight);
9 t* {, W# T8 {7 m( R, R7 _
}
- C, j2 ?) ] ~' C& }) L
}
7 D$ B* N2 ~* V' A+ u
}
' y9 A. ^3 L% A) [
0 e B# A+ S0 c- H9 ]6 N
int main() {
8 s M6 N3 v- O" O9 B$ B0 H
int vertex_count = 4; // 顶点数 5 I8 S5 j8 P5 \% e3 T- V+ U9 s- a
Edge edges[] = {
; Q( j3 d0 r9 c: W1 i5 j' T
{0, 1, 10},
W' u9 a8 b0 D7 K5 [
{0, 2, 6},
( X2 e U, @( R9 H( Z' C. B
{0, 3, 5},
- r* G7 H2 [" e
{1, 3, 15}, * r6 t; I, M$ n* m: _; `- _
{2, 3, 4}
! U x+ {# N- q7 T7 ?! U
};
* u" U' M. {# v
int edge_count = sizeof(edges) / sizeof(edges[0]);
+ c0 U1 l- [" V& |% F1 T( p1 w( n
2 _2 k! C4 h2 a
kruskal(edges, edge_count, vertex_count);
2 T1 H4 e3 F/ y4 e
: v2 H7 C- D5 b- }2 ]( R
return 0; j( ]0 W# E0 V: U3 Q
}

复制代码