Disjoint-set data structure: Difference between revisions

Revision as of 04:18, 24 December 2005

Revision as of 04:31, 24 December 2005

Line 73:

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.

=== FindingTracking the [[Connected component (graph theory)|connected components]] of an [[undirected graph]] ===

Suppose we have an [[undirected graph]] and we want to efficiently make queries regarding the [[Connected component (graph theory)|connected component]]s of that graph, such as:

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.

* Are two vertices of the graph in the same connected component?

Next, we simply visit each vertex and use '''Union''' to union its set with the sets of all its neighbors. Once this is done, we will have one group for each connected component, and can use '''Find''' to determine which connected component a particular vertex is in, or whether two vertices are in the same connected component.

* List all vertices of the graph in a particular component.

* How many connected components are there?

If the graph is static (not changing), we can simply use [[breadth-first search]] to associate a component with each vertex. However, if we want to keep track of these components while adding additional vertices and edges to the graph, a disjoint-set data structure is much more efficient.

Next,We weassume simplythe visitgraph eachis empty initially. Each time we add a vertex, andwe use '''UnionMakeSet''' to unionmake itsa set withcontaining only that vertex. Each time we add an edge, we use '''Union''' to union the sets of allthe itstwo neighbors.vertices Onceincident thisto isthat doneedge. Now, weeach set will havecontain onethe groupvertices forof eacha single connected component, and we can use '''Find''' to determine which connected component a particular vertex is in, or whether two vertices are in the same connected component.

This technique is used by the [[Boost Graph Library]] to implement its [http://www.boost.org/libs/graph/doc/incremental_components.html Incremental Connected Components] functionality.

Note that this scheme doesn't allow deletion of edges — even without path compression or the rank heuristic, this is not as easy, although more complex schemes have been designed that can deal with this type of incremental update.

=== Computing shorelines of a terrain ===