Dynamic connectivity - jaredgorski.org

Back to notes

Dynamic connectivity

Keywords: data structures, algorithms, computing, graph theory, graph, connected components
Date:
  • 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