next up previous
Next: One-to-all Shortest Paths Up: KRUSKAL'S ALGORITHM Previous: Weighted Union

Compressed Find

figure241

Lemma: The number of link operations done by a UNION-FIND program of length n implemented with W-UNION and C-FIND is O(nG(n)).

eqnarray244



Sushil Prasad
Thu Nov 4 14:09:59 EST 1999