Comparison Mode
Side-by-side: use case, requirements, complexity, strengths, weaknesses, example problems, and a clear “choose this when…”.
BFS vs DFSDijkstra vs Bellman-FordKruskal vs PrimMerge Sort vs Quick SortHeap vs Priority QueueHash Map vs Tree MapBFS vs DijkstraSliding Window vs Two PointersPrefix Sum vs Segment TreeGreedy vs Dynamic ProgrammingMemoization vs TabulationTarjan vs KosarajuSegment Tree vs Fenwick TreeArray vs Linked ListStack vs QueueQuick Sort vs Heap SortKMP vs Rabin-KarpUnion-Find vs DFSTrie vs Hash MapAVL Tree vs Red-Black Tree
TarjanGraph Algos | KosarajuGraph Algos | |
|---|---|---|
| Use case | Strongly connected components in a single DFS. | Strongly connected components with two simple DFS passes. |
| Requirements | Discovery times, low-link values, an explicit stack and an on-stack flag. | The reversed graph and a finish-order stack from the first pass. |
| Time complexity | O(V + E). | O(V + E). |
| Space complexity | O(V) for the arrays and stack. | O(V + E) for the transposed adjacency list. |
| Strengths | One pass; no reversed graph; SCCs come out in reverse topological order of the condensation. | Conceptually simple; each pass is a plain DFS; components emerge in topological order of the condensation. |
| Weaknesses | Low-link bookkeeping is easy to get wrong under interview pressure; deep recursion. | Builds a second graph; two traversals instead of one. |
| Example problems | Critical connections (low-link variant), 2-SAT, condensation graph of a directed graph. | Number of SCCs, checking if a directed graph is strongly connected, mother vertex. |
| Choose this when | Choose Tarjan when you want one pass, cannot afford the transposed graph, or already track low-links for bridges/articulation points. | Choose Kosaraju when clarity matters more than a constant factor; two plain DFS passes are easy to explain and debug. |