Path-based strong component algorithm
In graph theory, the Cheriyan–Mehlhorn/Gabow algorithm is a linear-time method for finding the strongly connected components of a directed graph.[1] It was discovered in 1996 by Joseph Cheriyan and Kurt Mehlhorn[2] and rediscovered in 1999 by Harold N. Gabow.[3]
Like Tarjan's strongly connected components algorithm, it performs a single depth first search of the given graph, using a stack to keep track of vertices that have not yet been assigned to a component, and moving these vertices into a new component when it finishes expanding the final vertex of its component. However, unlike Tarjan's algorithm, which uses a vertex-indexed array of preorder numbers to keep track of when to form a new component, Gabow's algorithm uses a second stack for this purpose.
Description
The algorithm performs a depth-first search of the given graph G, maintaining as it does two stacks S and P. 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, recursively search w;
- Otherwise, if w has not yet been assigned to a strongly connected component:
- 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.
References
- ^ 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.
- ^ Cheriyan, J.; Mehlhorn, K. (1996), "Algorithms for dense graphs and networks on the random access computer", Algorithmica, 15: 521–549.
- ^ Gabow, H.N. (2003), "Searching (Ch 10.1)", in Gross, J. L.; Yellen, J. (eds.), Discrete Math. and its Applications: Handbook of Graph Theory, vol. 25, CRC Press, pp. 953–984.