Kosaraju's Algorithm - Strongly Connected Components
source link: https://www.geeksforgeeks.org/videos/kosarajus-algorithm-strongly-connected-components/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Strongly Connected Components
- 50 Views
- 30/05/2022
A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph. For example, there are 3 SCCs in the following graph.
We can find all strongly connected components in O(V+E) time using Kosaraju’s algorithm. Following is detailed Kosaraju’s algorithm.
1) Create an empty stack ‘S’ and do DFS traversal of a graph. In DFS traversal, after calling recursive DFS for adjacent vertices of a vertex, push the vertex to stack. In the above graph, if we start DFS from vertex 0, we get vertices in stack as 1, 2, 4, 3, 0.
Kosaraju's Algorithm - Strongly Connected Components: https://www.geeksforgeeks.org/strongly-connected-components/
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK