Algoritma Kruskal

kruskal
Procedure
Kruskal(E, T : Sequence of Edge, P : UnionFind)
sort E by increasing edge weight
foreach {u, v} ∈ E do
if u, v are in different components of P then
add edge {u, v} to T
join the partitions of u and v in P


Procedure
filterKruskal(E, T : Sequence of Edge, P : UnionFind)
if m ≤ kruskalThreshold(n, |E|, |T |) then
Kruskal(E, T, P)
else
pick a pivot p ∈ E
E_:= he ∈ E : e ≤ pi E>:= he ∈ E : e > pi FilterKruskal(E_, T, P)
E>:= filter(E>, P)
FilterKruskal(E>, T, P)
Function Filter(E, P : UnionFind)
return
h{u, v} ∈ E : u, v are in different components of Pi