Exercise: Practice Tarjan’s Algorithm

The task at hand

Grab a paper and a pen, and figure out what are the stack contents right before each SSC of the following graph is identified by Tarjan’s algorithm. Assume that depth-first search is implemented to visit the vertices with smaller subscripts first.

You may verify your solution by clicking the “Run Tarjan’s Algorithm” 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).