Tarjan: Difference between revisions
Content added Content deleted
(Tarjan's strongly connected components algorithm) |
(Tarjan's strongly connected components algorithm) |
||
Line 1: | Line 1: | ||
{{task}} |
|||
{{wikipedia|Graph}} |
|||
[[Category:Algorithm]] |
|||
Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected components of a graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm. Tarjan's Algorithm is named for its discoverer, Robert Tarjan. |
Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected components of a graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm. Tarjan's Algorithm is named for its discoverer, Robert Tarjan. |