-
Notifications
You must be signed in to change notification settings - Fork 0
Union Find
Bruno Fernandes edited this page Dec 8, 2018
·
5 revisions
The IUnionFind structures can be used to
- connect hashable nodes with
Union, or - query whether they belong to the same connected component with
Connected.
They are commonly used to build algorithms to solve dynamic connectivity problems.
Two implementations are provided:
| Implementation \ Operation | Connected | Union |
|---|---|---|
QuickFind |
Constant | Linear |
QuickUnion |
Logarithmic | Logarithmic |
QuickFind should only be used when the number of reads will far outweigh the number of writes.
Both implementations occupy as much space as there are nodes.
n.b. The nodes of the problem space must be supplied ahead of time.