Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Algorithm

Tarjan's Strongly Connected Components Algorithm

Graph Algorithm

Tarjan's strongly connected components algorithm finds the strongly connected components of a directed graph, the maximal sets of vertices each reachable from every other vertex in the same set, in a single depth-first traversal. It runs in linear time, matching the time bound of alternative methods such as Kosaraju's algorithm, and is named for its inventor, Robert Tarjan, who published it in 1972 in Depth-first search and linear graph algorithms. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/

Facts
Time Complexity
O(V+E), linear in the number of vertices and edges. 2
Credited To
Robert Tarjan, 1972 (Depth-first search and linear graph algorithms, SIAM Journal on Computing, volume 1, issue 2). 2
Time Complexity
Time Complexity (category)
Linear Time -- O(n) 1
Connections

Credited To

Robert Tarjan, Pioneers
Source Wikipedia: Tarjan's Strongly Connected Components Algorithm

In Field

Algorithms and Complexity Theory, Fields
Source Wikipedia: Tarjan's Strongly Connected Components Algorithm

Invented By

Robert Tarjan, Pioneers

Robert Tarjan published his linear-time algorithm for finding strongly connected components of a directed graph in 1972, based on depth-first search.

Source Wikipedia: Robert Tarjan

Uses Design Technique

Recursion, Concepts
Source Wikipedia: Tarjan's Strongly Connected Components Algorithm
Sources
1. Tarjan's Strongly Connected Components Algorithm (Wikipedia)
Wikipedia infobox: time complexity linear
Quote, Wikipedia infobox: time complexity linear
linear
View the Source
2. Wikipedia: Tarjan's Strongly Connected Components Algorithm
Wikimedia Foundation
  • Lead section
    Tarjan's strongly connected components algorithm is an algorithm in graph theory for finding the strongly connected components (SCCs) of a directed graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm. The algorithm is named for its inventor, Robert Tarjan.
  • Body, complexity discussion
    linear in the number of edges and nodes in G
  • Body, references
    his original work was published in 1972 in a paper titled Depth-first search and linear graph algorithms in the SIAM Journal on Computing, volume 1, issue 2, pages 146-160
  • Uses Design Technique: Recursion, Article body
    Unlike in depth-first search, when the depth-first search recursively visits a node v and its descendants, those nodes are not all necessarily popped from the stack when this recursive call returns.
  • In Field: Algorithms and Complexity Theory, Lead sentence
    Tarjan's strongly connected components algorithm is an algorithm in graph theory for finding the strongly connected components (SCCs) of a directed graph.
  • Credited To: Robert Tarjan, Lead paragraph
    The algorithm is named for its inventor, Robert Tarjan.
View the Source
Wikidata: Tarjan's Strongly Connected Components Algorithm
Wikidata Q1972285, class allow-list match (w-wdresolver-0926)View the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.