Tardžanov algoritam za nalaženje jako povezanih komponenti

Tardžanov algoritam za nalaženje jako povezanih komponenti

Animacija Tardžanovog algoritma
Структура података	Graf
Најгора перформанца	$O(|V|+|E|)$

Tardžanov algoritam (nazvan po svom pronalazaču, Robertu Tardžanu) je algoritam teorije grafova, za nalaženje jako povezanih komponenti u grafu. Iako prethodi hronološki, može se smatrati poboljšanom verzijom Kosarajuovog algoritma, i može se porediti po efikasnosti sa algoritmom za nalaženje jakih komponenti, zasnovanim na putu.

Pregled

Algoritam na ulazu dobija usmeren graf, a na izlazu daje particiju čvorova grafa u jakim komponentama grafa. Svaki čvor grafa se pojavljuje u jednoj jako povezanoj komponenti, čak i ako to znači da se čvor pojavljuje u jako povezanoj komponenti sam (kao što je slučaj sa drvolikim delovima grafa, ili kad čvor nema ni prethodnika ni sledbenika).

Osnovna ideja algoritma je sledeća: obilazak u dubinu počinje od proizvoljnog čvora (i sledeće pretrage u dubinu su sprovedene na svakom čvoru koji nije još uvek pronađen). Pretraga ne ispituje čvorove koji su vec ispitani. Jako povezane komponente formiraju podstabla stabla pretrage, korenove od kojih su korenovi jako povezane komponente.

Čvorovi se stavljaju na stek, po redosledu u kom su posećeni. Kad se pretraga vrati iz podstabla, čvorovi se skidaju sa steka i određeno je da li je svaki čvor koren jako povezane komponente. Ako je čvor koren jako povezane komponente, tada i svi čvorovi koji su skinuti pre njega formiraju tu jako povezanu komponentu.

Svojstva korena

Srž algoritma je u određivanju da li je čvor koren jako povezane komponente. Koncept "korena" primenjuje se samo na ovaj algoritam (van ovog algoritma, nijedna jako povezana komponenta nema "koreni" čvor). Koreni čvor je jednostavno prvi čvor jako povezane komponente koji je posećen tokom pretrage u dubinu. Kada je čvor identifikovan kao koreni čvor, jednom kada se rekurzija nad njegovim sledbenikom završi, svi čvorovi na steku iznad korena formiraju kompletnu jako povezanu komponentu.

Da bi se pronašao koren, svakom čvoru pridružen je indeks pretrage u dubinu, v.index, koji numeriše čvorove uzastopno u redosledu u kojem su posećeni. Pored toga, svakom je dodeljena vrednost v.lowlink koja je jednaka najmanjem indeksu čvora koji je dostižan iz v, i uvek je manja ili jednaka v.index, ako nijedan drugi čvor nije dostižan iz v. Stoga je v koren jako povezane komponente ako i samo ako je v.lowlink == v.index. Vrednost v.lowlink je izračunata tokom pretrage u dubinu, tako da je uvek poznat kad je potreban.

Algoritam u pseudokodu

 ulaz: graf G = (V, E)
 izlaz: skup jako povezanih komponenti (skupovi čvorova)
  index := 0
 S := empty
 for each v in V do
   if (v.index je nedefinisan) then
     strongconnect(v)
   end if
 repeat
 function strongconnect(v)
   // Postavlja index za v na najmanji neiskorisćeni index
   v.index := index
   v.lowlink := index
   index := index + 1
   S.push(v)
  // Razmatranje sledbenika čvora v
   for each (v, w) in E do
     if (w.index is undefined) then
       // Sledbenik w nije posećen, rekurzija kreće iz njega
       strongconnect(w)
       v.lowlink := min(v.lowlink, w.lowlink)
     else if(w is in S) then
       // Sledbenik w je u steku S i stoga je u trenutnoj JPK
       v.lowlink := min(v.lowlink, w.index)
     end if
   repeat
  // Ako je v koreni čvor, skini sa steka i generiši JPK
   if (v.lowlink = v.index) then
     započni novu povezanu komponentu
     repeat
       w := S.pop()
       dodaj w trenutnoj jako povezanoj komponenti
     until (w = v)
     stavi na izlaz jako povezanu komponentu
   end if
 end function

Promenljiva index je brojač čvorova u pretrazi u dubinu. S je stek čvorova, koji počinje prazan i skladišti čvorove koji su posećeni ali još uvek nisu priključeni jako povezanoj komponenti. Primetiti da ovo nije klasičan stek pretrage u dubinu, jer se čvorovi ne skidaju pri vraćanju pretrage uz drvo; oni se jedino skidaju kada je nađena cela jako povezana komponenta.

Spoljašnja petlja traži svaki čvor koji jos nije posećen, i osigurava da čvorovi koji nisu dostižni iz prvog čvora su i dalje eventualno pređeni. Funkcija strongconnect vrši jednu pretragu u dubinu grafa, nalazeći sve sledbenike čvora v, i prijavljuje sve jako povezane komponente tog podgrafa.

Kada svaki čvor završi rekurziju, ako je njegov lowlink i dalje postavljen na njegov index, tada je on koreni čvor jako povezane komponente, formirane od svih čvorova iznad u steku. Algoritam skida sa steka i uključuje trenutni čvor, i prikazuje sve ove čvorove kao jako povezanu komponentu.

Primedbe

1. Složenost: Tardžanova procedura se poziva jednom za svaki čvor; za sve naredbe razmatra čvor najviše dva puta. Stoga je složenost linearna po broju grana u grafu, tj. $O(|V|+|E|)$.
2. Testiranje da li je w u steku trebalo bi biti gotovo u konstantnom vremenu, na primer testiranjem zastavice koja za svaki čvor označava da li je taj čvor u steku.
3. Iako nema ničeg specijalnog u redosledu čvorova u svakoj jako povezanoj komponenti, jedno korisno svojstvo algoritma je da nijedna jako povezana komponenta nece biti identifikovana pre svog sledbenika. Dakle, redosled po kome su jako povezane komponente identifikovane predstavlja obrnuto topološko sortiranje UAG, formiranog od jako povezanih komponenti.

Literatura

• Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979), „A linear-time algorithm for testing the truth of certain quantified boolean formulas”, Information Processing Letters, 8 (3): 121—123, doi:10.1016/0020-0190(79)90002-4 .
• Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2001). Introduction to Algorithms. Second Edition. MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3.  Section 22.5, pp. 552-557.}-

Spoljašnje veze

• Description of Tarjan's Algorithm
• Implementation of Tarjan's Algorithm in .NET
• Implementation of Tarjan's Algorithm in .NET (GitHub)
• Implementation of Tarjan's Algorithm in PHP
• Another implementation of Tarjan's Algorithm in Python
• Implementation of Tarjan's Algorithm in Javascript
• Java implementation for computation of strongly connected components in the jBPT library (see StronglyConnectedComponents class).