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.