Finding the Strong Components in a Directed Graph

摘要

The document presents two improved versions of Tarjan's algorithm for finding thestrongly connected components in a directed graph. The original algorithm can be considered to contain two traversals of the graph. First, a depth-first search traverses all edges of the graph and constructs a depth-first spanning forest. Second, once a root of a strong component is found, all its descendants that are not elements of previously found strong components are marked as elements of this component. The second traversal is implemented by using a pushdown stack, where all nodes are pushed when entered by the depth-first search. The authors' versions of the algorithm minimize the use of the pushdown stack. The first version stores only those nodes that are not roots of strong components. The second version stores only possible roots of nontrivial (containing at least one cycle) components. For graphs that are almost trees or dags these improvements almost completely eliminate the second traversal.