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.

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.

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?