実際、このアルゴリズムに関するHabréに関する記事はすでにありますが、アルゴリズムの正しさの証明といくつかのステップについては説明していません。私は、完全な分析を使用して、その記事のより参照バージョンを作成することにしました。
この投稿は、「アルゴリズムとグラフ理論」の分野の学生だけでなく、グラフ上のアルゴリズムの知識を向上/更新したい人にも役立ちます。
コサラユのアルゴリズムを理解するには、グラフ理論のいくつかの概念を知る必要があります
基本概念
グラフGにパス（必ずしも直線である必要はありません）が含まれている場合、頂点u、vは強く接続されていると呼ばれますu→vおよびv→u（強く接続されている頂点をu↔vで表します）
強く接続されたコンポーネントは、含めることによって最大の強く接続されたサブグラフです。
グラフの反転-グラフ内のすべてのエッジの方向を反対方向に変更します（双方向エッジはそれ自体のままです）
グラフの反転-エッジを反対方向に回転させるプロセス（双方向エッジはそれ自体のままになります）
いくつかのかなり明白な補題を引用することができます：
1.強く接続されたコンポーネントは、
少なくとも1つの共通の頂点を持つ一連のサイクルに含まれる一連の頂点です。
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) .
, .
例：トランスポートネットワークをグラフに投影します。このアルゴリズムは、新しく作成されたトランスポートネットワークで、各頂点から各頂点に到達できるかどうかを確認するのに役立ちます（周辺から中心および後方へのパスがあることを確認するため）。
アルゴリズムを使用して、建物のダクトシステムをテストできます。半導体デバイスの電流の流れ
より広く考えることができます。私たちは、2077年のどこかで、遺伝子工学プロジェクトの一環として作成するように指示された生物の循環システムを投影します。このアルゴリズムは、血液が心臓から臓器に行き来しているかどうかを調べるのに役立ちます。