Tarjan's strongly connected components algorithm
From Wikipedia, the free encyclopedia
Tarjan's Algorithm (named for its discoverer, Robert Tarjan) is a graph theory algorithm for finding the strongly connected components of a graph.
Contents |
[edit] Idea
The basic idea of the algorithm is this: a depth-first search begins from a start node. The strongly connected components form the subtrees of the search tree, the roots of which are the roots of the strongly connected components.
The nodes are placed on a stack in the order in which they are visited. When the search returns from a subtree, the nodes are taken from the stack and it is determined whether each node is the root of a strongly connected component. If a node is the root of a strongly connected component, then it and all of the nodes taken off before it form that strongly connected component.
[edit] The root property
The crux of the algorithm comes in determining whether a node is the root of a strongly connected component. To do this, each node is given a depth search index v.index, which numbers the nodes consecutively in the order in which they are discovered. In addition, each node is assigned a value v.lowlink that satisfies v.lowlink := min {v'.index: v' is reachable from v}. Therefore v is the root of a strongly connected component if and only if v.lowlink = v.index. The value v.lowlink is computed during the depth first search such that it is always known when needed.
[edit] The algorithm in pseudocode
Input: Graph G = (V, E), Start node v0 index = 0 // DFS node number counter S = empty // An empty stack of nodes tarjan(v0) // Start a DFS at the start node procedure tarjan(v) v.index = index // Set the depth index for v v.lowlink = index index = index + 1 S.push(v) // Push v on the stack forall (v, v') in E do // Consider successors of v if (v'.index is undefined) // Was successor v' visited? tarjan(v') // Recurse v.lowlink = min(v.lowlink, v'.lowlink) elseif (v' in S) // Is v' on the stack? v.lowlink = min(v.lowlink, v'.index) if (v.lowlink == v.index) // Is v the root of an SCC? print "SCC:" repeat v' = S.pop print v' until (v' == v)
[edit] Remarks
- Complexity: The tarjan procedure is called once for each node; the forall statement considers each edge at most twice. The algorithm's running time is therefore linear in the number of edges in G (O(|V|+|E|)).
- The test for whether v' is on the stack should be done in constant time, for example, by testing a flag stored on each node that indicates whether it is on the stack.
- The algorithm can only find those strongly connected components that are reachable from the start node. This can be overcome by starting the algorithm several times from different start nodes.
[edit] Literature
- Robert Tarjan: Depth-first search and linear graph algorithms. In: SIAM Journal on Computing. Vol. 1 (1972), No. 2, P. 146-160.