Lecture
Kosaraju's algorithm(Kosaraju) (named after the American scientist of Indian origin Sambasiva Rao Kosaraju — an algorithm for finding the strongly connected components in a directed graph. To find the strongly connected components, a depth-first search (DFS) is first performed on the reverse of the original graph (that is, against the arcs), computing the order in which vertices are finished. Then we use the reverse of this order to perform a depth-first search on the original graph (again taking the vertex with the largest number obtained in the reverse pass). The trees in the resulting DFS forest are the strongly connected components.
A directed acyclic graph — is a directed graph containing no directed cycles.
Finding the strongly connected components became possible thanks to depth-first search on a directed graph. The algorithm described here was proposed independently by Kosaraju in 1979.
To find the strongly connected components, a depth-first search is first performed on the reverse of the original graph, computing the order in which vertices are finished. Then we use the reverse of this order to perform a depth-first search on the original graph (again taking the vertex with the largest number obtained in the reverse pass). The trees in the resulting DFS forest are the strongly connected components.
This algorithm works on two series of depth-first searches (breadth-first search would also do), and therefore runs in time O(n + m)
Kosaraju's method finds the strongly connected components of a graph in linear time and memory.
Proof: This method consists of two depth-first search procedures subjected to minor modifications; as a result its running time is proportional to V² in the case of dense graphs and V + E in the case of sparse graphs (if the graphs are represented as adjacency lists).
Consider two adjacent strongly connected components in G (image on the right). Let f(v) – be the finishing order for vertex v in the DFS run. Then:
The proof uses the fact that the meta-graph (the condensed graph), in which all strongly connected components are contracted to a single vertex, is acyclic.
Corollary: the largest value of f will be in the source component (English source SCC), that is, the vertex will lie at the top of the stack.
If the input graph is described by an adjacency list, the algorithm performs two full traversals of the graph, and therefore runs in Θ(V+E) (linear) time, which is optimal, since it matches the lower bound (every algorithm must traverse all vertices and edges). This is conceptually the simplest efficient algorithm, but not as fast as Tarjan's algorithm and the path-based strong-component algorithm, which perform only a single traversal of the graph.
If the graph is represented by an adjacency matrix, the algorithm requires time Ο(V 2 ) .
Below is an example of how Kosaraju's algorithm works.
To compute the strongly connected components of the directed graph located at the bottom left, we first perform a depth-first search on its reverse (top left), computing the vector of the reverse traversal order (Order). This order is equivalent to the reverse traversal order of the DFS forest. Using the reverse of this order, we perform a depth-first traversal on the original graph. That is, we start from vertex 3. The trees in the DFS forest that are selected as a result of this process are the strongly connected components. The contents of the vector id: the component number; the digits on the left — the vertex number.
Comments