Kosarajus algoritm

Inom datavetenskap är Kosaraju-Sharirs algoritm (även känd som Kosarajus algoritm ) en linjär tidsalgoritm för att hitta de starkt sammankopplade komponenterna i en riktad graf . Aho , Hopcroft och Ullman krediterar det till S. Rao Kosaraju och Micha Sharir . Kosaraju föreslog det 1978 men publicerade det inte, medan Sharir upptäckte den självständigt och publicerade den 1981. Den använder sig av det faktum att transponeringsgrafen ( samma graf med riktningen för varje kant omvänd) har exakt samma starkt sammankopplade komponenter som den ursprungliga grafen.

Algoritmen

De primitiva grafoperationerna som algoritmen använder är att räkna upp grafens hörn, att lagra data per vertex (om inte i själva grafdatastrukturen, så i någon tabell som kan använda hörn som index), att räkna upp de yttre grannarna av en vertex (traverserande kanter i riktning framåt), och för att räkna upp in-grannarna till en vertex (traversera kanter i riktning bakåt); det sista kan dock göras utan, till priset av att konstruera en representation av transponeringsgrafen under den framåtgående traverseringsfasen. Den enda ytterligare datastruktur som behövs av algoritmen är en ordnad lista $L$ av grafens hörn, som kommer att växa till att innehålla varje vertex en gång.

Om starka komponenter ska representeras genom att utse en separat rotpunkt för varje komponent, och tilldela varje vertex rotpunkten för dess komponent, så kan Kosarajus algoritm anges enligt följande.

$u$ som obesökt för varje hörn $u$ i grafen . Låt $L$ vara tom.
För varje hörn u i grafen gör Visit(u) , där Visit(u) är den rekursiva subrutinen:
Om du är obesökt då:
1. Markera $dig$ som besökt.
2. För varje utomstående $v$ till $u$ , om $v$ är obesökt, gör Visit(v) .
3. Lägg $u$ till $L$ .
Annars gör ingenting.
För varje element u av L i ordning, gör Assign(u,u) där Assign(u,root) är den rekursiva subrutinen:
Om du inte har tilldelats en komponent så:
1. Tilldela $u$ som tillhörande komponenten vars rot är $root$ .
2. För varje in-granne $v$ av $u$ , gör Tilldela(v,root) .
Annars gör ingenting.

Triviala variationer är att istället tilldela ett komponentnummer till varje vertex, eller att konstruera per-komponent listor över de hörn som hör till den. Den obesökta/besökta indikationen kan dela lagringsplats med den slutliga tilldelningen av rot för en vertex.

Nyckelpunkten med algoritmen är att under den första (framåt) genomgången av grafkanterna läggs hörn före listan $L$ i efterföljande ordning i förhållande till sökträdet som utforskas. Detta betyder att det inte spelar någon roll om ett vertex $v$ först besöktes eftersom det förekom i uppräkningen av alla hörn eller för att det var utkanten till en annan vertex $u$ som fick besök; på båda håll kommer $v att läggas till$ $L$ före $u$ är, så om det finns en framåtriktad väg från $u$ till $v$ då kommer $u$ att synas före $v$ på den slutliga listan $L$ (om inte $u$ och $v$ båda tillhör samma starka komponent, i vilket fall deras relativa ordning i $L$ är godtycklig).

Detta innebär att varje element $n$ i listan kan fås att motsvara ett block $L[i n -1 : i n]$ , där blocket består av alla hörn som kan nås från vertex $n$ med bara utåtriktade kanter vid varje nod i väg. Det är viktigt att notera att ingen vertex i blocket som börjar på $n$ har en inåtgående länk från något av blocken som börjar vid någon vertex till höger, dvs blocken som motsvarar hörn $i n, i n +1, ... N$ i listan. Detta är så, för annars skulle vertexet som har den inåtriktade länken (säg från blocket som börjar på $n' \geq i n +1$ ) redan ha besökts och prependerat till $L$ i blocket av $n'$ , vilket är en motsägelse. Å andra sidan kan hörn i blocket som börjar vid $n$ ha kanter som pekar mot blocken som börjar vid någon vertex i ${i n, i n +1, \dots N}.$

Steg 3 i algoritmen, startar från $L[0]$ , tilldelar alla hörn som pekar på den, samma komponent som $L[0]$ . Observera att dessa hörn bara kan ligga i blocket som börjar vid $L[0]$ eftersom högre block inte kan ha länkar som pekar på hörn i blocket av $L[0]$ . Låt mängden av alla hörn som pekar mot $L[0]$ vara $In(L[0])$ . Därefter läggs även alla hörn som pekar mot dessa hörn, $In(In(L[0]))$ till, och så vidare tills inga fler hörn kan läggas till.

Det finns en väg till $L[0]$ , från alla hörn som lagts till komponenten som innehåller $L[0]$ . Och det finns en väg till alla hörn som läggs till från $L[0]$ , eftersom alla de ligger i blocket som börjar vid $L[0]$ (som innehåller alla hörn som kan nås från $L[0]$ efter utåtriktade kanter vid varje steg av banan) . Därför bildar alla dessa en enda starkt sammankopplad komponent. Dessutom finns ingen vertex kvar, eftersom för att vara i denna starkt anslutna komponent måste en vertex vara nåbar från $L[0]$ och måste kunna nå $L[0]$ . Alla hörn som kan nå $L[0]$ , om några, ligger endast i det första blocket, och alla hörn i det första blocket kan nås från $L[0]$ . Algoritmen väljer alltså alla hörn i den anslutna komponenten av $L[0]$ .

När vi når vertex $v = L[i]$ , i slingan i steg 3, och $v$ inte har tilldelats någon komponent, kan vi vara säkra på att alla hörn till vänster har gjort sina anslutna komponenter; att $v$ inte tillhör någon av dessa komponenter; att $v$ inte pekar på någon av hörnen till vänster om den. Dessutom, eftersom det inte finns någon kant från högre block till $v$ :s block, förblir beviset detsamma.

Som nämnts ovan använder algoritmen för enkelhet djup-först-sökning , men den kan lika gärna använda bredd-först-sökning så länge som efterbeställningsegenskapen bevaras.

Algoritmen kan förstås som att den identifierar den starka komponenten i ett vertex $u$ som en uppsättning av hörn som kan nås från $u$ både genom att gå bakåt och framåt. Skriv $F (u)$ för uppsättningen av hörn som kan nås från $u$ genom att korsa framåt, $B (u)$ för uppsättningen av hörn som kan nås från $u$ genom att gå bakåt och $P (u)$ för den uppsättning av hörn som visas strikt före $u$ på listan $L$ efter fas 2 av algoritmen är den starka komponenten som innehåller en vertex $u$ utsedd som rot

B(u)\cap F(u)=B(u)\setminus (B(u)\setminus F(u))=B(u)\setminus P(u).

Mängd skärningspunkt är beräkningsmässigt kostsam, men den är logiskt ekvivalent med en dubbelmängdsdifferens , och eftersom $B(u)\setminus F(u)\subseteq P( u)$ blir det tillräckligt att testa om ett nyligen påträffat element av $B (u)$ redan har tilldelats en komponent eller inte.

Komplexitet

Förutsatt att grafen beskrivs med hjälp av en närliggande lista , utför Kosarajus algoritm två fullständiga genomgångar av grafen och körs så i Θ(V+E) (linjär) tid, vilket är asymptotiskt optimalt eftersom det finns en matchande nedre gräns (vilken algoritm som helst måste undersöka alla hörn och kanter). Det är den konceptuellt enklaste effektiva algoritmen, men är inte lika effektiv i praktiken som Tarjans starkt sammankopplade komponentalgoritm och den vägbaserade starka komponentalgoritmen , som endast utför en genomgång av grafen.

Om grafen representeras som en närliggande matris kräver algoritmen Ο(V ² ) tid.

Alfred V. Aho , John E. Hopcroft , Jeffrey D. Ullman . Datastrukturer och algoritmer . Addison-Wesley, 1983.
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , Clifford Stein . Introduktion till algoritmer , 3:e upplagan. The MIT Press, 2009. ISBN 0-262-03384-4 .
Micha Sharir . En stark anslutningsalgoritm och dess tillämpningar för dataflödesanalys. Datorer och matematik med tillämpningar 7(1):67–72, 1981.

externa länkar

Bra matematik, dålig matematik: Beräkning av starkt anslutna komponenter