CarlNorfleet88 at 09:48, 8 September 2025

2025-09-08T09:48:15Z

New page

{{Short description|Method of finding a directed graph's strongly connected components}}
{{no footnotes|date=July 2020}}
In [[computer science]], '''Kosaraju-Sharir's algorithm''' (also known as '''Kosaraju's algorithm''') is a [[linear time]] [[algorithm]] to find the [[strongly connected component]]s of a [[directed graph]]. [[Alfred V. Aho|Aho]], [[John E. Hopcroft|Hopcroft]] and [[Jeffrey D. Ullman|Ullman]] credit it to [[S. Rao Kosaraju]] and [[Micha Sharir]].<ref>{{Cite book |last=Aho |first=Alfred V. |title=Data structures and algorithms |last2=Hopcroft |first2=John E. |last3=Ullman |first3=Jeffrey D. |date=1999 |publisher=Addison-Wesley |isbn=978-0-201-00023-8 |edition=Repr. with corrections |series=Addison-Wesley series in computer science and information processing |location=Reading, Mass.}}</ref><ref>{{Cite book |last=Cormen |first=Thomas H. |title=Introduction to algorithms |last2=Leiserson |first2=Charles Eric |last3=Rivest |first3=Ronald Linn |last4=Stein |first4=Clifford |date=2009 |publisher=MIT Press |isbn=978-0-262-03384-8 |edition=3rd |location=Cambridge, Massachusetts London, England}}</ref> Kosaraju suggested it in 1978 but did not publish it, while Sharir independently discovered it and published it in 1981.<ref>{{Cite journal |last=Sharir |first=M. |date=1981 |title=A strong-connectivity algorithm and its applications in data flow analysis |url=https://linkinghub.elsevier.com/retrieve/pii/0898122181900080 |journal=Computers & Mathematics with Applications |language=en |volume=7 |issue=1 |pages=67–72 |doi=10.1016/0898-1221(81)90008-0|url-access=subscription }}</ref> 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.

==The algorithm==
The primitive [[graph operations]] that the algorithm uses are to enumerate the vertices of the graph, to store data per vertex (if not in the graph [[data structure]] itself, then in some table that can use vertices as indices), to enumerate the out-neighbours of a vertex (traverse edges in the forward direction), and to enumerate the in-neighbours of a vertex (traverse edges in the backward direction); however the last can be done without, at the price of constructing a representation of the transpose graph during the forward traversal phase. The only additional data structure needed by the algorithm is an ordered list {{math|L}} of graph vertices, that will grow to contain each vertex once.

If strong components are to be represented by appointing a separate root vertex for each component, and assigning to each vertex the root vertex of its component, then Kosaraju's algorithm can be stated as follows.
# For each vertex {{mvar|u}} of the graph, mark {{mvar|u}} as unvisited. Let {{math|L}} be empty.
# For each vertex {{mvar|u}} of the graph do {{code|Visit(u)}}, where {{code|Visit(u)}} is the recursive subroutine:
#: If {{mvar|u}} is unvisited then:
#:# Mark {{mvar|u}} as visited.
#:# For each out-neighbour {{mvar|v}} of {{mvar|u}}, do {{code|Visit(v)}}.
#:# Prepend {{mvar|u}} to {{math|L}}.
#: Otherwise do nothing.
# For each element {{mvar|u}} of {{math|L}} in order, do {{code|Assign(u,u)}} where {{code|Assign(u,root)}} is the recursive subroutine:
#: If {{mvar|u}} has not been assigned to a component then:
#:# Assign {{mvar|u}} as belonging to the component whose root is {{mvar|root}}.
#:# For each in-neighbour {{mvar|v}} of {{mvar|u}}, do {{code|Assign(v,root)}}.
#: Otherwise do nothing.
Trivial variations are to instead assign a component number to each vertex, or to construct per-component lists of the vertices that belong to it. The unvisited/visited indication may share storage location with the final assignment of root for a vertex.

The key point of the algorithm is that during the first (forward) traversal of the graph edges, vertices are prepended to the list {{math|L}} in [[Tree_traversal#Post-order|post-order]] relative to the search tree being explored. This means it does not matter whether a vertex {{mvar|v}} was first visited because it appeared in the enumeration of all vertices or because it was the out-neighbour of another vertex {{mvar|u}} that got visited; either way {{mvar|v}} will be prepended to {{math|L}} before {{mvar|u}} is, so if there is a forward path from {{mvar|u}} to {{mvar|v}} then {{mvar|u}} will appear before {{mvar|v}} on the final list {{math|L}} (unless {{mvar|u}} and {{mvar|v}} both belong to the same strong component, in which case their relative order in {{math|L}} is arbitrary).

This means, that each element {{mvar|n}} of the list can be made to correspond to a block {{math|L[''i''{{sub|''n''-1}}: ''i''{{sub|''n''}}]}}, where the block consists of all the vertices reachable from vertex {{mvar|n}} using just outward edges at each node in the path. It is important to note that no vertex in the block beginning at {{mvar|n}} has an inward link from any of the blocks beginning at some vertex to its right, i.e., the blocks corresponding to vertices {{math|''i''{{sub|''n''}}, ''i''{{sub|''n''+1}}, … ''N''}} in the list. This is so, because otherwise the vertex having the inward link (say from the block beginning at {{math|''n' '' ≥ ''i''{{sub|''n''+1}}}}) would have been already visited and pre-pended to {{math|L}} in the block of {{mvar|n'}}, which is a contradiction. On the other hand, vertices in the block starting at {{mvar|n}} '''can have''' edges pointing to the blocks starting at some vertex in {{math|{''i''{{sub|''n''}}, ''i''{{sub|''n''+1}}, … ''N''}.}}

Step 3 of the algorithm, starts from {{math|L[0]}}, assigns all vertices which point to it, the same component as {{math|L[0]}}. Note that these vertices can only lie in the block beginning at {{math|L[0]}} as higher blocks can't have links pointing to vertices in the block of {{math|L[0]}}. Let the set of all vertices that point to {{math|L[0]}} be {{math|In(L[0])}}. Subsequently, all the vertices pointing to these vertices, {{math|In(In(L[0]))}} are added too, and so on till no more vertices can be added.

There is a path to {{math|L[0]}}, from all the vertices added to the component containing {{math|L[0]}}. And there is a path to all the vertices added from {{math|L[0]}}, as all those lie in the block beginning at {{math|L[0]}} (which contains all the vertices reachable from {{math|L[0]}} following outward edges at each step of path). Hence all these form a single strongly connected component. Moreover, no vertex remains, because, to be in this strongly connected component a vertex must be reachable from {{math|L[0]}} and must be able to reach {{math|L[0]}}. All vertices that are able to reach {{math|L[0]}}, if any, lie in the first block only, and all the vertices in first block are reachable from {{math|L[0]}}. So the algorithm chooses all the vertices in the connected component of {{math|L[0]}}.

When we reach vertex {{math|1=v = L[''i'']}}, in the loop of step 3, and {{mvar|v}} hasn't been assigned to any component, we can be sure that all the vertices to the left have made their connected components; that {{mvar|v}} doesn't belong to any of those components; that {{mvar|v}} doesn't point to any of the vertices to the left of it. Also, since, no edge from higher blocks to {{mvar|v}}'s block exists, the proof remains same.

As given above, the algorithm for simplicity employs [[depth-first search]], but it could just as well use [[breadth-first search]] as long as the post-order property is preserved.

The algorithm can be understood as identifying the strong component of a vertex {{mvar|u}} as the set of vertices which are reachable from {{mvar|u}} both by backwards and forwards traversal. Writing {{math|''F''(''u'')}} for the set of vertices reachable from {{mvar|u}} by forward traversal, {{math|''B''(''u'')}} for the set of vertices reachable from {{mvar|u}} by backwards traversal, and {{math|''P''(''u'')}} for the set of vertices which appear strictly before {{mvar|u}} on the list {{mvar|L}} after phase 2 of the algorithm, the strong component containing a vertex {{mvar|u}} appointed as root is
: <math> B(u) \cap F(u) = B(u) \setminus (B(u) \setminus F(u)) = B(u) \setminus P(u).</math>
Set intersection is computationally costly, but it is logically equivalent to a double [[set difference]], and since {{tmath|B(u) \setminus F(u) \subseteq P(u)}} it becomes sufficient to test whether a newly encountered element of {{math|''B''(''u'')}} has already been assigned to a component or not.

== Complexity ==
Provided the graph is described using an [[adjacency list]], Kosaraju's 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 the [[path-based strong component algorithm]], which perform only one traversal of the graph.

If the graph is represented as an [[adjacency matrix]], the algorithm requires ''Ο(V<sup>2</sup>)'' time.

== References ==
<references />

== External links ==
*[http://scienceblogs.com/goodmath/2007/10/30/computing-strongly-connected-c/ Good Math, Bad Math: Computing Strongly Connected Components]

[[Category:Graph algorithms]]
[[Category:Graph connectivity]]

Kosaraju's algorithm - Revision history

CarlNorfleet88 at 09:48, 8 September 2025