Kosarajus algoritme (til ære for den amerikanske videnskabsmand af indisk oprindelse Sambasiva Rao Kosaraju) er en algoritme til at finde stærkt forbundne områder i en rettet graf . For at finde områder med stærk forbindelse udføres først dybde-først-søgning (DFS) på inversionen af den originale graf (det vil sige mod buerne), idet udgangsrækkefølgen fra hjørnerne beregnes. Derefter bruger vi denne rækkefølge-inversion til at udføre en dybde-først-søgning på den originale graf (igen tager vi toppunktet med det maksimale antal opnået under tilbageløbet). De træer i DFS-skoven, der udvælges som følge heraf, er stærke komponenter.
En rettet acyklisk graf er en rettet graf, der ikke indeholder rettede cyklusser.
Kosaraju-metoden giver en søgning efter stærke forbundne komponenter i en graf i lineær tid og hukommelse.
Bevis: Denne metode består af to dybde-første-første-første-første-første-første-første-første-første-første-første-første-sæt-rutiner, med mindre ændringer, så dens køretid er proportional med V² i tilfælde af mættede grafer og V + E i tilfælde af sparsomme grafer (hvis graferne er repræsenteret som lister over tilstødende hjørner).
Nedenfor er et eksempel på driften af Kosaraju-algoritmen.
For at beregne de stærke komponenter i en nederst til venstre rettet graf, laver vi først en dybde-først søgning på dens bagside (øverst til venstre), og beregner vektoren for den omvendte gennemløbsrækkefølge (orden). Denne rækkefølge svarer til den omvendte rækkefølge af at krydse DFS-skoven. Ved at bruge inversionen af denne rækkefølge udfører vi en dybde-først gennemgang på den originale graf. Det vil sige, at vi starter ved node 3. Træerne i DFS-skoven, som er udvalgt som følge af denne proces, er stærke komponenter. Indholdet af id vektoren er nummeret på komponenten, tallene til venstre er nummeret på toppunktet.