Union-Find

Each group is a tree, named by its root. To see if two items are in one group, compare their roots; to merge two groups, hang one root under the other. Nothing is relabelled or recounted.

P19 Union-Find1×

Example problem: count the connected groups after a list of connections.

looking at nowroot of a group

Each element is its own root

parent = [0, 1, 2, 3, 4]groups = –a = –b = –rootA = –rootB = –x = –

01/41

restart · back · play · step

Speed

1function countGroups(n, connections):

2 parent = [0, 1, ..., n - 1]

3 groups = n

4 for (a, b) in connections:

5 rootA = find(a)

6 rootB = find(b)

7 if rootA is not rootB:

8 parent[rootB] = rootA

9 groups = groups - 1

10 return groups

12function find(x):

13 while parent[x] is not x:

14 x = parent[x]

15 return x

← → step · space play/pause

How to recognise

items that only ever get connected, never split, and questions like "how many groups?", "are a and b connected?" or "which edge closes a cycle?".

How to solve problems like this

Make every item its own group: parent[x] = x.
Write find(x): follow parent until you reach an item that is its own parent. That item is the root.
To connect a and b, find both roots. If they differ, set one root as the parent of the other and count one group less.
Keep the trees flat: inside find, point each node you pass straight at the root, and hang the smaller tree under the bigger one.

Where it's used

Finding objects in a picture. OpenCV (connectedComponents) and SciPy (ndimage.label) find connected spots of pixels: neighbouring pixels are joined into one group, and then each group gets a number.
Splitting a photo into regions. Felzenszwalb's algorithm, which scikit-image has, merges neighbouring pixels into regions when they look alike, and keeps the regions in a union-find.