TheAlgorithms
[FEATURE REQUEST] Tarjan's Algorithm Implementation
What would you like to Propose?
There's no implementation of Tarjan's algorithm under the graphs section. So, I'd like to contribute.
Issue details
As an undirected graph may have connected components, a directed graph may have strongly connected components (SCC).
A graph is said to be strongly connected if every vertex is reachable from every other vertex. The SCCs of a directed graph form a partition into subgraphs that are themselves strongly connected. A single node is always an SCC.
Tarjan's algorithm aims at finding the SCCs. We also have Kosaraju's algorithm which does the same but requires two DFS traversals while Tarjan's algorithm solves the problem in a single DFS traversal.
Tarjan's algorithm idea is similar to the algorithm for articulation point detection. On the other hand, Kosaraju's is quite similar to the idea of finding the topological sorting of a graph.
Tarjan’s algorithm has much lower constant factors compared to Kosaraju’s algorithm. Since DFS is done at least 2 times in Kosaraju’s algorithm, the constant factor is double the time. We can print the SCC in progress with Kosaraju’s algorithm as we perform the second DFS. While performing Tarjan’s Algorithm, it requires extra time to print the SCC after finding the head of the SCCs sub-tree.
Additional Information
No response
