Union-find is not just an interview data structure. It lives inside graph libraries, image processing, compilers and data-cleaning pipelines. This chapter shows how real libraries expose it, lists common mistakes, and points to further reading.
Union-find in libraries
Before writing your own, check whether a library you already use provides one.
- SciPy:
scipy.cluster.hierarchy.DisjointSet (since SciPy 1.6) accepts any hashable object as an element, not just integers. - NetworkX:
networkx.utils.UnionFind is used internally, for example by its Kruskal minimum spanning tree implementation. - Boost: the C++ Boost Graph Library provides
boost::disjoint_sets, used for incremental connected components. - Image processing: connected-component labeling such as scikit-image's
label or OpenCV's connectedComponents relies on the same idea to merge provisional labels in the classic two-pass algorithm.
from scipy.cluster.hierarchy import DisjointSet
ds = DisjointSet(["a", "b", "c", "d"])
ds.merge("a", "b")
ds.merge("c", "d")
print(ds.connected("a", "c")) # False
ds.add("e")
ds.merge("b", "e")
print(sorted(map(sorted, ds.subsets()))) # [['a', 'b', 'e'], ['c', 'd']]
Where it shows up in real systems
- Networks and infrastructure: tracking which devices can reach each other as links are added.
- Data cleaning and entity resolution: grouping records that share a phone number, email or device ID into one customer.
- Compilers and type checkers: unification in type inference and Steensgaard-style points-to analysis merge things proven to be "the same" with union-find.
- Physics simulations: percolation experiments open random grid cells and check whether the top and bottom have become connected.
- Clustering: merging every pair of points closer than a threshold gives the same result as single-linkage clustering.
Handling string keys
Real data rarely comes with integer keys. Number each new key with a dictionary and the array-based DSU works unchanged.
class KeyedDSU:
def __init__(self):
self.index, self.parent, self.size = {}, [], []
def _id(self, key):
if key not in self.index:
self.index[key] = len(self.parent)
self.parent.append(len(self.parent))
self.size.append(1)
return self.index[key]
def find(self, key):
x = self._id(key)
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
d = KeyedDSU()
d.union("phone:555-0100", "mail:kim@x.io")
d.union("mail:kim@x.io", "device:A7")
print(d.find("phone:555-0100") == d.find("device:A7")) # True
Common pitfalls
- Linking non-roots: writing
parent[a] = b corrupts the sets. Always link the roots returned by find. - Comparing parents to test membership:
parent[a] == parent[b] can be wrong before paths are compressed. Always use find(a) == find(b). - One-based numbering: if vertices are numbered from 1, allocate n+1 slots or subtract 1.
- Deep recursion: a recursive find in Python raises RecursionError on large inputs. Use a loop.
- Deletion and undo: the basic structure cannot split sets. If you need undo, use a rollback DSU, which drops path compression and records each change on a stack.
class RollbackDSU:
def __init__(self, n):
self.parent, self.size, self.history = list(range(n)), [1] * n, []
def find(self, x): # no path compression, so changes stay undoable
while self.parent[x] != x:
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.history.append((rb, ra) if ra != rb else None)
if ra != rb:
self.parent[rb] = ra
self.size[ra] += self.size[rb]
def rollback(self):
last = self.history.pop()
if last:
rb, ra = last
self.parent[rb] = rb
self.size[ra] -= self.size[rb]
Summary
Union-find already powers SciPy, NetworkX and Boost, as well as image labeling, type inference and data cleaning. Three habits prevent most bugs: link roots, compare with find, and implement find with a loop. When you need undo, reach for a rollback DSU.
Further reading
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.