Nothing special here. It’s just a blog post for summarising my algorithm learning course.
- Part 1 - Union Find: This post
- Part 2 - Quick Find
- Part 3 - Quick Union
- Part 4 - Improved Quick Union
- Part 5 - Related Interview Questions
Dynamic Connectivity
The problem
Given a data structure organised as a set of N objects
- Union command: connect 2 objects.
- Find/connected command: is there a path connecting 2 objects?
union(4, 3);
union(3, 8);
union(6, 5);
union(9, 4);
union(2, 1);
connected(0, 7) return false;
connected(8, 9) return true;
union(5, 0);
union(7, 2);
union(6, 1);
union(1, 0);
connected(0, 7) return true;
Can only answer the question with Yes
or No
. The Dynamic Connectivity
implementation cannot
answer the exact path between 2 objects. It can only answer whether there are any paths connecting 2
objects.
IsConnected Relation
IsConnected
relation has these properties
- Reflexive: p is connected to p.
- Symmetric: if p is connected to q, then q is connected to p.
- Transitive: if p is connected to q and q is connected to r, then p is connected to r.
Connected Components
Maximal set of objects that are mutually connected
3 connected components
- { 0 }
- { 1 4 5 }
- { 2 3 6 7 }
Union Find
The Union Find data type contains these 2 main methods
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? |