Path-based strong component algorithm
In graph theory, the strongly connected components of a directed graph may be found using an algorithm that uses depth-first search in combination with two stacks, one to keep track of the vertices in the current component and the second to keep track of the current search path.[1] Versions of this algorithm have been proposed by (Purdom 1970), (Munro 1971), (Dijkstra 1976), (Cheriyan Mehlhorn), and (Gabow 2000); of these, Dijkstra's version was the first to achieve linear time.[2]
Description
The algorithm performs a depth-first search of the given graph G, maintaining as it does two stacks S and P (in addition to the normal call stack for a recursive function). Stack S contains all the vertices that have not yet been assigned to a strongly connected component, in the order in which the depth-first search reaches the vertices. Stack P contains vertices that have not yet been determined to belong to different strongly connected components from each other. It also uses a counter C of the number of vertices reached so far, which it uses to compute the preorder numbers of the vertices.
When the depth-first search reaches a vertex v, the algorithm performs the following steps:
- Set the preorder number of v to C, and increment C.
- Push v onto S and also onto P.
- For each edge from v to a neighboring vertex w:
- If the preorder number of w has not yet been assigned (the edge is a tree edge), recursively search w;
- Otherwise, if w has not yet been assigned to a strongly connected component (the edge is a forward/back/cross edge):
- Repeatedly pop vertices from P until the top element of P has a preorder number less than or equal to the preorder number of w.
- If v is the top element of P:
- Pop vertices from S until v has been popped, and assign the popped vertices to a new component.
- Pop v from P.
The overall algorithm consists of a loop through the vertices of the graph, calling this recursive search on each vertex that does not yet have a preorder number assigned to it.
Related algorithms
Like this algorithm, Tarjan's strongly connected components algorithm also uses depth first search together with a stack to keep track of vertices that have not yet been assigned to a component, and moves these vertices into a new component when it finishes expanding the final vertex of its component. However, in place of the stack P, Tarjan's algorithm uses a vertex-indexed array of preorder numbers, assigned in the order that vertices are first visited in the depth-first search. The preorder array is used to keep track of when to form a new component.
Notes
- ↑ (Sedgewick 2004).
- ↑ History of Path-based DFS for Strong Components, Harold N. Gabow, accessed 2012-04-24.
References
- Cheriyan, J. (1996), "Algorithms for dense graphs and networks on the random access computer", Algorithmica 15 (6): 521–549, doi:10.1007/BF01940880.
- A Discipline of Programming, NJ: Prentice Hall, 1976, Ch. 25.
- "Path-based depth-first search for strong and biconnected components", Information Processing Letters 74 (3–4): 107–114, 2000, doi:10.1016/S0020-0190(00)00051-X, https://www.cs.princeton.edu/courses/archive/spr04/cos423/handouts/path%20based...pdf.
- "Efficient determination of the transitive closure of a directed graph", Information Processing Letters 1 (2): 56–58, 1971, doi:10.1016/0020-0190(71)90006-8.
- Purdom, P., Jr. (1970), "A transitive closure algorithm", BIT 10: 76–94, doi:10.1007/bf01940892, http://digital.library.wisc.edu/1793/57514.
- Sedgewick, R. (2004), "19.8 Strong Components in Digraphs", Algorithms in Java, Part 5 – Graph Algorithms (3rd ed.), Cambridge MA: Addison-Wesley, pp. 205–216.
 |  |
