Graph Algorithms the Fun Way

C UNION-FIND

Kruskal’s algorithm, randomized maze generation, and single-linkage clustering from Chapter 10 all use a data structure called UnionFind to represent the disjoint sets of nodes corresponding to the different connected components in a graph. This data structure allows the algorithms to efficiently (1) determine whether two nodes are already in the same connected component and (2) merge two different components. For completeness, this appendix describes and provides the code for this data structure.

We begin by providing a very brief overview of union-find data structures, followed by just enough code to implement the algorithms ...