Computer scienceAlgorithms and Data StructuresAlgorithmsGraph algorithmsConnectivity algorithms

Kosaraju's algorithm

Theory

The steps of Kosaraju's algorithm

Report a typo

Put the steps below in the order that reconstructs Kosaraju's algorithm for a graph GG.

Put the items in the correct order
Choose an unvisited node with the maximum output time and run DFS from this node for transposed GG.
Repeat two previous steps until the graph contains no unvisited nodes.
Transpose GG.
Run DFS for GG and save output time for each node.
When the current iteration of DFS is finished, save the nodes visited during the iteration as a strongly connected component.
___

Create a free account to access the full topic