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
- the set of vertices
- 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
andy
?"- AKA, "do vertices
x
andy
belong to the same connected component?
- AKA, "do vertices
- 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