union-find

These are notes from a great course on algorithms.

Slides

Slides

Use Case

Give a set of objects, determine if they are connected

Interface

• UF(int N): initialize union-find data structure with N objects (0 to N – 1)
• void union(int p, int q): add connection between p and q
• boolean connected(int p, int q): are p and q in the same component?
• int find(int p): component identifier for p (0 to N – 1)
• int count(): number of components

Quick find implementation

Use integer array id[] of length N p and q are connected if they have same id id[p]==id[q]

• UF(int N): id[i]=i
• boolean connected(int p, int q): id[p]==id[q]
• void union(int p, int q): change all id[p] to id[q]

Quick union (lazy)

Use integer array id[] of length N id[i] is the parent of i Root of i id id[id[id[…id[i]…]]]

• UF(int N): id[i]=i
• boolean connected(int p, int q): Check if p and q have the same root. root(p) == root(q)
• void union(int p, int q): To merge components containing p and q, set the id of p’s root to the id of q’s root. id[root(p)]=root(q)
• private int root(int i): iterate i=id[i] until i==id[i]

Issue: trees can become too deep

Quick union (weighted)

Add an array to track size of item at i

• UF(int N): id[i]=i
• boolean connected(int p, int q): Check if p and q have the same root. root(p) == root(q)
• void union(int p, int q): Link root of smaller tree to root of larger tree

   int i = root(p);
   int j = root(q);
   if (i == j) return;
   if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
   else { id[j] = i; sz[i] += sz[j]; } 
  

• private int root(int i): iterate i=id[i] until i==id[i]

Analysis: Running time.

• Find: takes time proportional to depth of p and q.
• Union: takes constant time, given roots. Proposition. Depth of any node x is at most lg N.

Quick union (path compression)

Quick union with path compression: Just after computing the root of p, set the id of each examined node to point to that root.
Two-pass implementation: add second loop to root() to set the id[] of each examined node to the root.
Simpler one-pass variant: Make every other node in path point to its grandparent (thereby halving path length)

• UF(int N): id[i]=i
• boolean connected(int p, int q): Check if p and q have the same root. root(p) == root(q)
• void union(int p, int q): Link root of smaller tree to root of larger tree

   int i = root(p);
   int j = root(q);
   if (i == j) return;
   if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
   else { id[j] = i; sz[i] += sz[j]; } 
  

• private int root(int i): iterate i=id[i] until i==id[i]

Analysis: Running time.

• Find: takes time proportional to depth of p and q.
• Union: takes constant time, given roots. Proposition. Depth of any node x is at most lg N.

Analysis

algorithm	initialize	union	find
quick-find	N	N	1
quick-union	N	N	N
quick-union (weighted)	N	lg N	lg N