In fact, there is already an article on Habré on this algorithm, but it does not cover the proof of the correctness and some steps of the algorithm. I decided to create a more reference version of that article with full analysis.
This post will be useful for students of the discipline "Algorithms and Graph Theory", as well as those who want to improve / refresh their knowledge of algorithms on graphs.
In order to understand Kosarayu's algorithm, you need to know some concepts of graph theory
Basic concepts
Vertices u, v are called strongly connected if the graph G contains a path (not necessarily a straight line) u → v And v → u (We denote strongly connected vertices by u↔v)
Strongly connected components are strongly connected subgraphs maximal with respect to inclusion.
Inverting the graph - changing the direction of all edges in the graph to the opposite (a bidirectional edge remains itself)
Inverting a graph - the process of turning edges in the opposite direction (a bidirectional edge will remain itself)
Several fairly obvious lemmas can be cited:
1. A strongly connected component is the set of vertices included in the set of cycles that
have at least one common vertex
2.
3. u ↔ v v ↔ w, u ↔ v ↔ w
4.
:
(DFS), «» . «», DFS ( ).
DFS
DFS .
DFS
, : : , :
DFS
( , , )
,
:
1:
'?'
DFS ( 2 , ; , , )
, - ( ) 1
, () ( ) -- DFS -- .
2:
3:
DFS, ,
DFS
3
, :
u v ⇔ DFS
:
⇒
u v G, ( 2), , .
⇐
u v . , r .
r 3 , 1 , u v. 2 :
r . u r v r ( 2). u v ( 3)
r , v. r v , r — ( , v , r, ). ( , ), , v r 3 ( )
, 1 2 , u v
O(V+E)
, , O(V+E) . ( )
, O(V+E)
, — O(V+E)
, O(V+E) .
, .
For example: projecting a transport network onto a graph. The algorithm will help to check the newly-made transport network for the reachability of each vertex from each vertex (to make sure that there is a path from the outskirts to the center and back).
You can test the duct system in buildings with an algorithm; current flow in semiconductor devices
You can think more broadly: we project the circulatory system of a living being, which you were instructed to create as part of a genetic engineering project, somewhere in 2077). The algorithm will help you find out if blood is getting from the heart to the organs and back.