Union–Find & Dijkstra

Graphs, lesson 3 of 3

Union–Find & Dijkstra

Merge groups in near-O(1) with union–find, and find cheapest weighted paths with a heap.

13 min, 0 of 4 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

Union–find (a.k.a. disjoint set union, DSU) tracks groups that only ever merge. Each group is a little tree; its root is the group's representative.

  • find(x): walk up parents to the root.
  • union(a, b): find both roots; if they differ, hang one under the other.

Two tricks make both operations nearly O(1) (amortised α(n), which is ≤ 4 for any real n):

  • path compression: after a find, point every node on the path straight at the root
  • union by rank: hang the shorter tree under the taller one, so trees stay flat

Reach for it when edges arrive one at a time and you keep asking "are these two already connected?", e.g. detecting the edge that creates a cycle in an undirected graph.

Example

A union–find class

union(0, 2) returns False: 0 and 2 were already linked through 1 and 3, so that edge would close a cycle. With union by rank a tree's height stays O(log n), so the recursive find never gets deep.

Walkthrough

The unions above, one edge at a time

0p=01p=12p=23p=34p=45p=5
Step 1 of 7
rank = [0, 0, 0, 0, 0, 0]

parent[x] = x: every node is the root of its own one-node group.

root
edge being added
merged two groups
ends already connected

p under each node is its parent.

Quiz

What does this print?

Weighted graphs need Dijkstra. When edges have different costs, BFS's "fewest edges" is no longer "cheapest": one 10-minute flight loses to three 1-minute hops.

Dijkstra's algorithm is BFS with a min-heap instead of a queue: always expand the node with the smallest known distance.

  1. dist[src] = 0, heap = [(0, src)].
  2. Pop (d, node). If d > dist[node] it's a stale entry (a better one was already handled): skip it.
  3. Relax each edge: if d + w < dist[nxt], update it and push (d + w, nxt).

Cost: O(E log V) with heapq. It requires non-negative weights.

Example

Dijkstra with heapq, traced

The direct edge 0 → 1 costs 4, but 0 → 2 → 1 costs 3, so (4, 1) becomes stale and is skipped. Once a node is popped with its true distance, it is settled: nothing cheaper can come later, because every other path starts from a node that is at least as far away.

Walkthrough

Dijkstra from 0

41215001∞2∞3∞
Step 1 of 7
heap = [(0, 0)]

dist[0] = 0, everything else is infinity.

popped now / edge improved a distance
settled
in the heap

Labels show dist; the heap is listed smallest first.

Quiz

What does this print?

Exercise

Connectivity queries

Write connected(n, edges, queries): nodes are 0..n-1, edges are undirected pairs and each query is a pair (a, b). Return a list of booleans, one per query: are a and b in the same component?

Use union–find: union every edge, then compare roots.

connected(5, [(0, 1), (1, 2), (3, 4)], [(0, 2), (0, 4)]) is [True, False].

Quiz

Edges of an undirected graph arrive one by one. After each, you must report whether it created a cycle. Best tool?