Graph Connectivity algorithms are algorithms that checks to see if a graph is connected. This means for any two vertices , there exists a path such that there exists where .
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||- extra space.|
|Breadth-First Search||- extra space.|
|Warshall's Algorithm||- in place.|
|Naive Union Find||- extra space.|
|Union Find with Path Compression||- extra space.|
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 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 , where is the inverse Ackermann function. This algorithm is simple, and if no delete is needed, can be run as an on-line algorithm.