I know both have runtime complexity $\mathcal{O} (V+E)$, but Tarjan's algorithm does a single DFS pass, whereas Kosaraju's does two DFS passes. Both need extra space (e.g. a dynamic set, often a stack, for the former to keep track of low links, and e.g. a linked list for the latter to do the second traversal in decreasing finish time order from the first traversal).

I often see textbooks (e.g. CLRS) describing Kosaraju's instead of Tarjan's algorithm. Maybe that's for pedagogical reasons, but I wonder if there is something else to it.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.