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.
Overview The algorithm takes a directed graph as input, and produces a partition of the graph's vertices into the graph's strongly connected components. Each vertex of the graph appears in exactly one of the strongly connected components. Any vertex that is not on a directed cycle forms a strongly connected component all by itself—i.e., any vertex whose in-degree or out-degree is 0, or every vertex of a directed acyclic graph. The basic idea of the algorithm is this: a depth-first search (DFS) begins from an arbitrary start node (and subsequent depth-first searches are conducted on any nodes that have not yet been found). As usual with depth-first search, the search visits every node of the graph exactly once, refusing to revisit any node that has already been visited. Thus, the collection of search trees is a spanning forest of the graph. The strongly connected components will be recovered as certain subtrees of this forest. The roots of these subtrees are called the "roots" of the strongly connected components. Any node of a strongly connected component might serve as a root, if it happens to be the first node of a component that is discovered by search.
Stack invariant The root of a strongly connected component with respect to a depth first search traversal is the first node in the component visited by the depth first search component. The root is therefore the last node in the component that is backtracked out of during the traversal. The key idea used in Tarjans algorithm is that a root can also be expressed as a node from which no previously visited node is reachable. As in standard depth first search, nodes are placed on a stack in the order in which they are visited. 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. The crucial invariant property is that a node remains on the stack after it has been visited if and only if there exists a path in the input graph from it to some node earlier on the stack, and nodes are removed when backtracking out of a root. In other words, a node is only removed from the DFS stack when all of its connected paths have been traversed. At the end of the call that visits v and its descendants, we know whether v itself has a path to any node earlier on the stack. If so, the call returns, leaving v on the stack to preserve the invariant. If not, then v must be the root of its strongly connected component, which consists of v together with any nodes later on the stack than v (such nodes all have paths back to v but not to any earlier node, because if they had paths to earlier nodes then v would also have paths to earlier nodes which is false). The connected component rooted at v is then popped from the stack and returned, again preserving the invariant.
Bookkeeping Each node v is assigned a unique integer v.index, which numbers the nodes consecutively in the order in which they are discovered. It also maintains a value v.lowlink that represents the smallest index of any node on the stack known to be reachable from v through v's DFS subtree, including v itself. Therefore v must be left on the stack if v.lowlink < v.index, whereas v must be removed as the root of a strongly connected component if v.lowlink == v.index. The value v.lowlink is computed during the depth-first search from v, as this finds the nodes that are reachable from v. The lowlink is different from the lowpoint, which is the smallest index reachable from v through any part of the graph.
The algorithm in pseudocode algorithm tarjan is input: graph G = (V, E) output: set of strongly connected components (sets of vertices) index := 0 S := empty stack for each v in V do if v.index is undefined then strongconnect(v) function strongconnect(v) // Set the depth index for v to the smallest unused index v.index := index v.lowlink := index index := index + 1 S.push(v) v.onStack := true // Consider successors of v for each (v, w) in E do if w.index is undefined then // Successor w has not yet been visited; recurse on it strongconnect(w) v.lowlink := min(v.lowlink, w.lowlink) else if w.onStack then // Successor w is in stack S and hence in the current SCC // If w is not on stack, then (v, w) is an edge pointing to an SCC already found and must be ignored // See below regarding the next line v.lowlink := min(v.lowlink, w.index) // If v is a root node, pop the stack and generate an SCC if v.lowlink = v.index then start a new strongly connected component repeat w := S.pop() w.onStack := false add w to current strongly connected component while w ≠ v output the current strongly connected component
… excerpt ends here. Continue reading the full article.
