A dynamic connectivity structure is a data structure that dynamically maintains information about the connected components of a graph. The set V of vertices of the graph is fixed, but the set E of edges can change. The three cases, in order of difficulty, are:
-
Edges are only added to the graph (this can be called incremental connectivity);
-
Edges are only deleted from the graph (this can be called decremental connectivity);
-
Edges can be either added or deleted (this can be called fully dynamic connectivity).
After each addition/deletion of an edge, the dynamic connectivity structure should adapt itself such that it can give quick answers to queries of the form "is there a path between x and y?" (equivalently: "do vertices x and y belong to the same connected component?").
-
Union command: connect two objects.
-
Find/Connected query: is there a path connecting the two objects?
union method call should bind two objects
union(p, q)
connected? method call should return boolean value showing are these objects connected or not
connected?(p, q)
root method call should return parent of all ancestors. Method is private thus it will be invoked only implicitly and only in cases when we have graph data structure(Quick Union with all its modifications)
root(p)
| Algorithms | Worst-case time |
|---|---|
| Quick Find(Eager approach) | M N |
| Quick union(Lazy approach) | M N |
| Quick union(Weighted improvement) | N + M log N |
| Quick union(Compression path improvement) | N + M log N |
| Quick union(Weighted + Compression path improvements) | N + M lg* N |