Disjoint-set data structure: Difference between revisions

Revision as of 00:58, 15 November 2004

Revision as of 17:16, 6 December 2004

Line 72:

Disjoint-set data structures arise naturally in many applications, particularly where some kind of partitioning or [[equivalence relation]] is involved, and this section discusses some of them.

=== Finding the [[connectedConnected component (graph theory)|connected components]]s of an [[undirected graph]] ===

Initially, we assume that every vertex in the graph is in its own connected component, and is not connected to any other vertex. To represent this, we use '''MakeSet''' to initially make a set for each vertex containing only that vertex.