Dynamic connectivity

• Dynamic connectivity refers to a data structure that dynamically reflects information about connections between vertices within a Graph
• In this data structure:
  • the set of vertices V is fixed
  • the set of edges E can change
• Types of dynamic connectivity:
  • incremental: edges are only added to the graph
  • decremental: edges are only removed from the graph
  • fully dynamic: edges are added or removed
• The dynamic connectivity structure should provide quick answers to the question “is there a path between x and y?”
  • AKA, "do vertices x and y belong to the same connected component?
• The dynamic connectivity structure should reflect any addition or removal of edges, such that its output is always current with the latest state of the graph it represents

Example

• Given a set of N objects:
  • Union command: connect two objects
  • Find/connected query: check if two given objects are connected

Build connections:

union(4, 3)
union(3, 8)
union(6, 5)
union(9, 4)
union(2, 1)

Query connections:

connected(0, 7) // false
connected(8, 9) // true

Build more connections:

union(5, 0)
union(7, 2)
union(6, 1)
union(1, 0)

Query again:

connected(0, 7) // now it's true

–> Source ↗