# "DisjointSet"(Data Structure) "DisjointSet"

represents a collection of elements that are general expressions and that are partitioned into disjoint sets.

# Details  • A disjoint set has efficient merging and removal as well as membership testing:
•  CreateDataStructure[ "DisjointSet"] create a new empty "DisjointSet" Typed[x,"DisjointSet"] give x the type "DisjointSet"
• For a data structure of type "DisjointSet", the following operations can be used:
•  ds["CommonSubsetQ",x,y] return True if x and y are in the same subset time: O(α(n)) ds["Copy"] return a copy of ds time: O(n) ds["Elements"] return a list of the elements of ds time: O(n) ds["EmptyQ"] True, if ds is empty time: O(1) ds["Find",x] return the parent of x time: O(α(n)) ds["Insert",x] add x to the collection of elements time: O(α(n)) ds["Length"] return the number of elements stored in ds time: O(1) ds["MemberQ",x] True, if x is an element of ds time: O(1) ds["Merge",dsi] merge the elements of dsi into ds time: O(n) ds["Remove",x] remove x from ds, return True if x was actually an element time: O(n) ds["Subsets"] return the subsets in ds time: O(n) ds["Unify",x,y] unify the subsets of x and y time: O(α(n)) ds["Visualization"] return a visualization of ds time: O(n)
• The following functions are also supported:
•  dsi===dsj True, if dsi equals dsj FullForm[ds] full form of ds Information[ds] information about ds InputForm[ds] input form of ds Normal[ds] convert ds to a normal expression
• Many operations such as insertion, merging and testing for common subsets have near constant-time performance, bounded by α(n), the inverse Ackermann function.

# Examples

open allclose all

## Basic Examples(1)

A new "DisjointSet" can be created with CreateDataStructure:

Initially there are no elements and no subsets:

Insert two elements; each goes into its own subset:

Unify the subsets:

Add two more elements and unify; now there are two subsets:

Unify the two subsets; now there is only one subset:

A visualization of the data structure can be generated:

## Scope(1)

### Information(1)

A new "DisjointSet" can be created with CreateDataStructure:

Information about the data structure ds:

## Applications(1)

### Kruskal Algorithm(1)

The minimum spanning tree of a graph is a tree that connects all the vertices with a minimum total edge weight. The Kruskal algorithm is one way to compute a minimum spanning tree, and it can be written to use a "DisjointSet".

An implementation of the Kruskal algorithm:

A graph to use to test the Kruskal implementation:

Compute the minimum spanning tree with the Kruskal algorithm:

Show how the minimum spanning tree maps onto the original graph: