Kosarajus algoritm (till ära av den amerikanske vetenskapsmannen av indiskt ursprung Sambasiva Rao Kosaraju) är en algoritm för att hitta starkt sammankopplade regioner i en riktad graf . För att hitta områden med stark anslutning utförs först djup-först-sökning (DFS) på inversionen av den ursprungliga grafen (det vill säga mot bågarna), och beräknar utgångsordningen från hörnen. Sedan använder vi denna ordningsinvertering för att utföra en djup-först-sökning på den ursprungliga grafen (återigen, vi tar vertexet med det maximala antalet erhållna under bakåtpassningen). De träd i DFS-skogen som väljs ut som ett resultat är starka komponenter.
En riktad acyklisk graf är en riktad graf som inte innehåller riktade cykler.
Kosaraju-metoden ger en sökning efter starka sammankopplade komponenter i en graf i linjär tid och minne.
Bevis: Denna metod består av två djup-först-första-första-första-första-första-första-första-första-första-första-första-första-uppsättningen-rutiner, med mindre modifieringar så att dess körtid är proportionell mot V² i fallet med mättade grafer och V + E i fallet med glesa grafer (om graferna representeras som listor över angränsande hörn).
Nedan är ett exempel på hur Kosaraju-algoritmen fungerar.
För att beräkna de starka komponenterna i en nedre vänstra graf, gör vi först en djup-först-sökning på dess baksida (överst till vänster), och beräknar vektorn för omvänd traverseringsordning (Order). Denna ordning motsvarar den omvända ordningen för att korsa DFS-skogen. Genom att använda inverteringen av denna ordning utför vi en genomgång av djupet-först på den ursprungliga grafen. Det vill säga vi börjar vid nod 3. Träden i DFS-skogen som väljs ut som ett resultat av denna process är starka komponenter. Innehållet i id-vektorn är komponentens nummer, siffrorna till vänster är numret på vertexet.