Kosarajun algoritmi (intialaista alkuperää olevan amerikkalaisen tiedemiehen Sambasiva Rao Kosarajun kunniaksi) on algoritmi vahvasti toisiinsa liittyvien alueiden löytämiseksi suunnatusta graafista . Vahvan liitettävyyden alueiden löytämiseksi suoritetaan ensin syvällinen haku (DFS) alkuperäisen graafin käänteisversiolla (eli kaaria vasten) laskemalla poistumisjärjestys pisteistä. Sitten käytämme tätä järjestysinversiota tehdäksemme syvyys-ensimmäisen haun alkuperäisestä graafista (jälleen otamme kärkipisteen, jonka enimmäismäärä on saatu taaksepäin ajon aikana). Tuloksena valitut DFS-metsän puut ovat vahvoja komponentteja.
Suunnattu asyklinen graafi on suunnattu graafi, joka ei sisällä suunnattuja syklejä.
Kosaraju-menetelmä tarjoaa graafin vahvasti toisiinsa liittyvien komponenttien etsinnän lineaarisessa ajassa ja muistissa.
Todistus: Tämä menetelmä koostuu kahdesta syvyys-ensin-ensin-ensin-ensin-ensin-ensin-ensin-ensin-ensin-ensin-ensin-ensin-ensin-ensin-ensin-ensin-sarjan -rutiinista pienin muutoksin, jotta sen ajoaika on verrannollinen V²:ään tyydyttyneiden graafien tapauksessa ja V + E:hen harvalukuisten graafien tapauksessa (jos graafit esitetään vierekkäisten kärkien listoina).
Alla on esimerkki Kosaraju-algoritmin toiminnasta.
Laskeaksemme alavasemmalle suunnatun graafin vahvat komponentit, teemme ensin syvyys-ensin haun sen käänteisestä (ylhäällä vasemmalla) laskemalla käänteisen läpikulkujärjestyksen vektorin (Order). Tämä järjestys vastaa käänteistä DFS-metsän läpikulkujärjestystä. Käyttämällä tämän järjestyksen käänteistä suoritamme alkuperäiselle kaaviolle syvyys-ensikierroksen. Eli aloitamme solmusta 3. Tämän prosessin tuloksena valitut DFS-metsän puut ovat vahvoja komponentteja. Id-vektorin sisältö on komponentin numero, vasemmalla olevat numerot ovat kärjen numero.