# Graph Connectivity

Graph Connectivity algorithms are algorithms that checks to see if a graph is connected. This means for any two vertices ${\displaystyle V_{i},V_{j}}$, there exists a path ${\displaystyle E_{1},\ldots ,E_{k}}$ such that there exists ${\displaystyle E_{1}=(V_{a_{1}},V_{a_{2}}),E_{2}=(V_{a_{2}},V_{a_{3}}),\ldots ,E_{x}=(V_{a_{x}},V_{a_{x+1}}),\ldots ,E_{k}=(V_{a_{k-1}},V_{a_{k}})}$ where ${\displaystyle a_{1}=i,a_{k}=j}$.

## Algorithms

There are many simple algorithms for Graph Connectivity problems, which makes it ideal for beginners.

### Graph Connectivity Algorithms and Complexities

 Algorithm Time Complexity Space Complexity Depth-First Search ${\displaystyle O(V+E)}$ ${\displaystyle O(V+E)}$ - ${\displaystyle O(V)}$ extra space. Breadth-First Search ${\displaystyle O(V+E)}$ ${\displaystyle O(V+E)}$ - ${\displaystyle O(V+E)}$ extra space. Warshall's Algorithm ${\displaystyle O(V^{3})}$ ${\displaystyle O(V^{2})}$ - in place. Naive Union Find ${\displaystyle O(V\log V)}$ ${\displaystyle O(V+E)}$ - ${\displaystyle O(V)}$ extra space. Union Find with Path Compression ${\displaystyle O(E\alpha (V))}$ ${\displaystyle O(V+E)}$ - ${\displaystyle O(V)}$ extra space.

### Depth-First Search

Depth-First Search allows the construction of a connectivity tree in ${\displaystyle O(V+E)}$ time. Though there is an added step, this approach works for both undirected and directed graphs.

Warshall's Algorithm, a narrower version of Floyd-Warshall's Algorithm can be used as a precalculation to store the adjacency matrix of graph. This runs in ${\displaystyle \Theta (V^{3})}$ time, but is particularly effective when the graph is dense, or if it's a static structure with little updates and a lot of queries.
Union Find is a data structure used for keeping tracks of partitioning distinct data sets. The way to use this for Graph Connectivity is by starting off with each vertex as its own set. Then we can process each edge as a join of two sets. The running time (with some optimizations) is ${\displaystyle O(E\alpha (V))}$, where ${\displaystyle \alpha ()}$ is the inverse Ackermann function. This algorithm is simple, and if no delete is needed, can be run as an on-line algorithm.