# Dynamic connectivity

## From Wikipedia, the free encyclopedia

In computing and graph theory, 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?").