Graph Connectivity

From Algorithmist
Jump to: navigation, search

Graph Connectivity algorithms are algorithms that checks to see if a graph is connected. This means for any two vertices V_{i},V_{j}, there exists a path E_{1},\ldots ,E_{k} such that there exists 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 a_{1}=i,a_{k}=j.

Algorithms[edit]

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

Graph Connectivity Algorithms and Complexities[edit]

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(V^{3}) O(V^{2}) - in place.
Naive Union Find O(V\log V) O(V+E) - O(V) extra space.
Union Find with Path Compression O(E\alpha (V)) O(V+E) - O(V) extra space.

Depth-First Search[edit]

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.

Breadth-First Search[edit]

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.

Warshall's Algorithm[edit]

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 \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[edit]

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\alpha (V)), where \alpha () is the inverse Ackermann function. This algorithm is simple, and if no delete is needed, can be run as an on-line algorithm.