Kosaraju algoritmusa (az indiai származású amerikai tudós, Sambasiva Rao Kosaraju tiszteletére) egy algoritmus az erősen összefüggő régiók megtalálására egy irányított gráfban . Az erős összeköttetésű területek megtalálásához a mélységi keresést (DFS) először az eredeti gráf megfordításán (vagyis az ívekkel szemben) hajtják végre, kiszámítva a csúcsokból a kilépési sorrendet. Ezután ezzel a sorrend-inverzióval végezzünk mélységi keresést az eredeti gráfon (ismét a visszafelé haladás során kapott maximális számú csúcsot vesszük fel). A DFS-erdő ennek eredményeként kiválasztott fái erős összetevők.
Az irányított aciklikus gráf olyan irányított gráf, amely nem tartalmaz irányított ciklusokat.
A Kosaraju módszer egy gráf erősen összefüggő összetevőinek keresését teszi lehetővé lineáris időben és memóriában.
Bizonyítás: Ez a módszer két mélységben-először-először-először-először-először-először-először-először-először-először-először-először-először-először-először-először-először-készlet-rutinból áll, kisebb módosításokkal, hogy a futási ideje telített gráfok esetén arányos V²-vel, ritka gráfok esetén pedig V + E-vel (ha a gráfokat szomszédos csúcsok listájaként ábrázoljuk).
Az alábbiakban egy példa látható a Kosaraju algoritmus működésére.
Egy balra lent irányított gráf erős összetevőinek kiszámításához először mélységi keresést végzünk a hátoldalán (bal felső sarokban), kiszámítva az inverz bejárási sorrendvektort (Order). Ez a sorrend megegyezik a DFS-erdő bejárásának fordított sorrendjével. Ennek a sorrendnek az inverzióját használva mélységi bejárást végzünk az eredeti gráfon. Vagyis a 3. csomópontnál kezdjük. A folyamat eredményeként kiválasztott DFS-erdő fái erős összetevők. Az id vektor tartalma a komponens száma, a bal oldali számok a csúcs száma.