Graph Connectivity
From Algorithmist
Graph Connectivity algorithms are algorithms that checks to see if a graph is connected. This means for any two vertices Vi,Vj, there exists a path 
such that there exists 
where a1 = i,a2 = j.
Contents |
[edit] Algorithms
There are many simple algorithms for Graph Connectivity problems, which makes it ideal for beginners.
[edit] Graph Connectivity Algorithms and Complexities
| Algorithm | Time Complexity | Space Complexity |
| Depth-First Search | O(V + E) | O(V + E) - O(V) extra space. |
| Breadth-First Search | O(V + E) | O(V + E) - O(V + E) extra space. |
| Warshall's Algorithm | O(V3) | O(V2) - in place. |
| Naive Union Find | O(VlogV) | O(V + E) - O(V) extra space. |
| Union Find with Path Compression | O(Eα(V)) | O(V + E) - O(V) extra space. |
[edit] Depth-First Search
Depth-First Search allows the construction of a connectivity tree in O(V + E) time. Though there is an added step, this approach works for both undirected and directed graphs.
[edit] Breadth-First Search
Breadth-First Search is another type of search, but can be utilized in pretty much the same way as Depth-First Search for the construction of a connectivity tree.
[edit] Warshall's Algorithm
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 Θ(V3) 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.
[edit] Union Find
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 O(Eα(V)), where α() is the inverse Ackermann function. This algorithm is simple, and if no delete is needed, can be run as an on-line algorithm.
