Kosaraju's algorithm
Encyclopedia
In computer science
, the Kosaraju-Sharir algorithm is an algorithm
to find the strongly connected component
s of a directed graph
. Aho, Hopcroft and Ullman credit it to an unpublished paper from 1978 by S. Rao Kosaraju
and Micha Sharir
. It makes use of the fact that the transpose graph
(the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph.
Kosaraju-Sharir algorithm is simple and works as follows:
, Kosaraju-Sharir algorithm performs two complete traversals of the graph and so runs in Θ(V+E) (linear) time, which is asymptotically optimal
because there is a matching lower bound (any algorithm must examine all vertices and edges). It is the conceptually simplest efficient algorithm, but is not as efficient in practice as Tarjan's strongly connected components algorithm
and Gabow's algorithm, which perform only one traversal of the graph.
If the graph is represented as an adjacency matrix
, the algorithm requires Ο(V2) time.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the Kosaraju-Sharir algorithm is an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
to find 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,...
. Aho, Hopcroft and Ullman credit it to an unpublished paper from 1978 by S. Rao Kosaraju
S. Rao Kosaraju
Sambasiva Rao Kosaraju is a professor of Computer Science at Johns Hopkins University, who has done extensive work in the design and analysis of parallel and sequential algorithms....
and Micha Sharir
Micha Sharir
Micha Sharir is a professor of computer science at Tel Aviv University, known for his work in computational geometry.After completing his undergraduate studies at Tel Aviv University in 1970, Sharir received a Ph.D. in mathematics from Tel Aviv in 1976 under the supervision of Aldo Lazar...
. It makes use of the fact that the transpose graph
Transpose graph
In the mathematical and algorithmic study of graph theory, the converse, transpose or reverse of a directed graph G is another directed graph on the same set of vertices with all of the edges reversed compared to the orientation of the corresponding edges in G...
(the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph.
Kosaraju-Sharir algorithm is simple and works as follows:
- Let G be a directed graph and S be an empty stackStack (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,...
. - While S does not contain all vertices:
- Choose an arbitrary vertex v not in S. Perform a depth-first searchDepth-first searchDepth-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....
starting at v. Each time that depth-first search finishes expanding a vertex u, push u onto S.
- Choose an arbitrary vertex v not in S. Perform a depth-first search
- Reverse the directions of all arcs to obtain the transpose graph.
- While S is nonempty:
- Pop the top vertex v from S. Perform a depth-first search starting at v. The set of visited vertices will give the strongly connected component containing v; record this and remove all these vertices from the graph G and the stack S. Equivalently, breadth-first searchBreadth-first searchIn graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes...
(BFS) can be used instead of depth-first search.
- Pop the top vertex v from S. Perform a depth-first search starting at v. The set of visited vertices will give the strongly connected component containing v; record this and remove all these vertices from the graph G and the stack S. Equivalently, breadth-first search
Complexity
Provided the graph is described using an adjacency listAdjacency list
In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list.If the graph is undirected, every entry is a set of two nodes containing the two ends of the corresponding edge; if it is directed, every entry is a tuple of two nodes, one denoting the source node...
, Kosaraju-Sharir algorithm performs two complete traversals of the graph and so runs in Θ(V+E) (linear) time, which is asymptotically optimal
Asymptotically optimal
In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor worse than the best possible algorithm...
because there is a matching lower bound (any algorithm must examine all vertices and edges). It is the conceptually simplest efficient algorithm, but is not as efficient in practice as 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...
and Gabow's algorithm, which perform only one traversal of the graph.
If the graph is represented as an adjacency matrix
Adjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
, the algorithm requires Ο(V2) time.