Dynamic Connectivity
Dynamic Connectivity
Given a set of N objects.
Union command: connect two objects.
Find/connected query: is there a path connecting the two objects?
Modelling the Connections
We assume "is connected to" is an equivalence relation:
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
Connected components: Maximal set of objects that are mutually connected.
Implementing Operations
Find Query: Check if two objects are in the same component.
Union command: Replace components containing two objects with their union.
Union Find Data Type - Java
Last updated