Exercise: Practice the Kosaraju-Sharir Algorithm
Test your understanding of the Kosaraju-Sharir algorithm.
We'll cover the following
The task at hand
Grab a pen and a piece of paper, and figure out how to use the two-pass Kosaraju-Sharir algorithm to find the SSCs of the following digraph. Assume that the depth-first search implementation picks vertices with smaller indices first.
Verify the solution in three steps by clicking the “Run FirstPassDFS of G” button.
Note:
- You may also try experimenting on a different digraph that can be created following these
instructions. instructions - If the automatically generated labels overlap with vertices or edges, you may view them more clearly by dragging the vertices of the given digraph (after selecting the “Drag vertices” checkbox).
Get hands-on with 1200+ tech skills courses.