Strongly Connected Components
Revision as of 11:01, 10 October 2022 by Admin (talk | contribs) (Created page with "== Problem Description== Connectivity in an undirected graph means that every vertex can reach every other vertex via any path. If the graph is not connected the graph can be broken down into Connected Components. Strong Connectivity applies only to directed graphs. A directed graph is strongly connected if there is a directed path from any vertex to every other vertex. This is same as connectivity in an undirected graph, the only difference being strong connectivity ap...")
Problem Description
Connectivity in an undirected graph means that every vertex can reach every other vertex via any path. If the graph is not connected the graph can be broken down into Connected Components.
Strong Connectivity applies only to directed graphs. A directed graph is strongly connected if there is a directed path from any vertex to every other vertex. This is same as connectivity in an undirected graph, the only difference being strong connectivity applies to directed graphs and there should be directed paths instead of just paths. Similar to connected components, a directed graph can be broken down into Strongly Connected Components.
Bounds Chart
Error creating thumbnail: Unable to save thumbnail to destination
Step Chart
Error creating thumbnail: Unable to save thumbnail to destination
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | ||
| Polynomial > 3 | ||
| Cubic | ||
| Quadratic | Paul Purdom; 1970 (1970) | |
| nlogn | Munro’s algorithm (1971) | |
| Linear | Kosaraju's algorithm (1978)
Tarjan's strongly connected components algorithm (1972) Path-based strong components algorithm; Dikjstra (1976) |
|
| logn |