Content deleted Content added
m Reverted 1 edit by 2A02:2F08:E70E:5400:ACF8:7683:51AE:E2FA (talk) to last revision by 2A02:2F08:E70E:5400:FD4C:61BB:1C5B:44F5 (TW) |
MazeChaZer (talk | contribs) m Introduce DFS abbreviation |
||
Line 17:
The algorithm takes a [[directed graph]] as input, and produces a [[Partition of a set|partition]] of the graph's [[Vertex (graph theory)|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: for example, a vertex whose in-degree or out-degree is 0, or any vertex of an 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, declining to revisit any node that has already been visited. Thus, the collection of search trees is a [[Spanning forest#Spanning forests|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 ===
| |||