Graph Connectivity

From Algorithmist
Jump to navigation Jump to search

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 .

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 - extra space.
Breadth-First Search - extra space.
Warshall's Algorithm - in place.
Naive Union Find - extra space.
Union Find with Path Compression - extra space.

Depth-First Search[edit]

Depth-First Search allows the construction of a connectivity tree in 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 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 , where is the inverse Ackermann function. This algorithm is simple, and if no delete is needed, can be run as an on-line algorithm.