Gabow's algorithm
Encyclopedia
In graph theory
, the Cheriyan–Mehlhorn/Gabow algorithm is a linear-time method for finding the strongly connected component
s of a directed graph
. It was discovered in 1996 by Joseph Cheriyan and Kurt Mehlhorn
and rediscovered in 1999 by Harold N. Gabow.
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. 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. Instead of the array, Gabow's algorithm uses a second stack for this purpose.
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:
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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the Cheriyan–Mehlhorn/Gabow algorithm is a linear-time method for finding the strongly connected component
Strongly connected component
A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular, this means paths in each direction; a path from a to b and also a path from b to a....
s of a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
. It was discovered in 1996 by Joseph Cheriyan and Kurt Mehlhorn
Kurt Mehlhorn
Kurt Mehlhorn is a German computer scientist. He has been a vice president of the Max Planck Society and is director of the Max Planck Institute for Computer Science.-Education:...
and rediscovered in 1999 by Harold N. Gabow.
Like Tarjan's strongly connected components algorithm
Tarjan's strongly connected components algorithm
Tarjan's Algorithm is a graph theory algorithm for finding the strongly connected components of a graph...
, it performs a single depth first search of the given graph, using a stack
Stack (data structure)
In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the 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. 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
Depth-first search
Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
. The preorder array is used to keep track of when to form a new component. Instead of the array, 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.