@graphty/algorithms / index / UnionFind
Class: UnionFind ​
Defined in: data-structures/union-find.ts:9
Union-Find (Disjoint Set) data structure with path compression and union by rank
Efficiently supports dynamic connectivity queries and is essential for algorithms like connected components and minimum spanning trees.
Constructors ​
Constructor ​
new UnionFind(
elements):UnionFind
Defined in: data-structures/union-find.ts:18
Creates a new UnionFind data structure with the given elements.
Parameters ​
elements ​
NodeId[]
Array of elements to initialize the data structure with
Returns ​
UnionFind
Methods ​
addElement() ​
addElement(
element):void
Defined in: data-structures/union-find.ts:165
Add a new element to the data structure
Parameters ​
element ​
The element to add as a new singleton set
Returns ​
void
connected() ​
connected(
elementA,elementB):boolean
Defined in: data-structures/union-find.ts:95
Check if two elements are in the same connected component
Parameters ​
elementA ​
The first element to check
elementB ​
The second element to check
Returns ​
boolean
True if both elements are in the same component, false otherwise
find() ​
find(
element):NodeId
Defined in: data-structures/union-find.ts:35
Find the root of the set containing the element with path compression
Parameters ​
element ​
The element to find the root for
Returns ​
The root element of the set containing the given element
getAllComponents() ​
getAllComponents():
NodeId[][]
Defined in: data-structures/union-find.ts:133
Get all connected components as separate arrays
Returns ​
NodeId[][]
Array of arrays, where each inner array contains elements of one component
getComponent() ​
getComponent(
element):NodeId[]
Defined in: data-structures/union-find.ts:116
Get all elements that belong to the same component as the given element
Parameters ​
element ​
The element whose component should be retrieved
Returns ​
NodeId[]
Array of all elements in the same component
getComponentCount() ​
getComponentCount():
number
Defined in: data-structures/union-find.ts:107
Get the number of connected components
Returns ​
number
The current count of disjoint components
getComponentSize() ​
getComponentSize(
element):number
Defined in: data-structures/union-find.ts:157
Get the size of the component containing the given element
Parameters ​
element ​
The element whose component size should be retrieved
Returns ​
number
The number of elements in the component containing the given element
hasElement() ​
hasElement(
element):boolean
Defined in: data-structures/union-find.ts:180
Check if an element exists in the data structure
Parameters ​
element ​
The element to check for
Returns ​
boolean
True if the element exists, false otherwise
size() ​
size():
number
Defined in: data-structures/union-find.ts:188
Get the total number of elements
Returns ​
number
The total count of all elements in the data structure
union() ​
union(
elementA,elementB):void
Defined in: data-structures/union-find.ts:60
Union two sets using union by rank
Parameters ​
elementA ​
The first element whose set should be merged
elementB ​
The second element whose set should be merged
Returns ​
void