Изворни код странице Tardžanov algoritam za nalaženje jako povezanih komponenti

{{Infobox algorithm
|class=
|image=[[Датотека:Tarjan's Algorithm Animation.gif|200p]]
|caption = Animacija Tardžanovog algoritma
|data=[[Graph (struktura podataka)|Graf]]
|time= <math>O(|V|+|E|)</math>
|best-time=
|average-time=
|space=
|optimal=
|complete=
}}
'''Tardžanov algoritam''' (nazvan po svom pronalazaču, [[Robert Tardžan|Robertu Tardžanu]]<ref>{{citation|first=R. E.|last=Tarjan|authorlink=Robert Tarjan|title=Depth-first search and linear graph algorithms|journal=[[SIAM Journal on Computing]]|volume=1|year=1972|issue=2|pages=146–160|doi=10.1137/0201010}}</ref>) je algoritam [[teorija grafova|teorije grafova]], za nalaženje jako povezanih komponenti u [[graf]]u. Iako prethodi hronološki, može se smatrati poboljšanom verzijom [[Kosaraju's algorithm|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: [[pretraga u dubinu|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, <tt>v.index</tt>, koji numeriše čvorove uzastopno u redosledu u kojem su posećeni. Pored toga, svakom je dodeljena vrednost <tt>v.lowlink</tt> koja je jednaka najmanjem indeksu čvora koji je dostižan iz <tt>v</tt>, i uvek je manja ili jednaka <tt>v.index</tt>, ako nijedan drugi čvor nije dostižan iz <tt>v</tt>. Stoga je <tt>v</tt> koren jako povezane komponente ako i samo ako je <tt>v.lowlink == v.index</tt>. Vrednost <tt>v.lowlink</tt> 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 <tt>index</tt> je brojač čvorova u pretrazi u dubinu. <tt>S</tt> 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 <tt>strongconnect</tt> vrši jednu pretragu u dubinu grafa, nalazeći sve sledbenike čvora <tt>v</tt>, i prijavljuje sve jako povezane komponente tog podgrafa.

Kada svaki čvor završi rekurziju, ako je njegov <tt>lowlink</tt> i dalje postavljen na njegov <tt>index</tt>, 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 ==
# 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. <math>O (|V| + |E|)</math>.
# 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.
# 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.<ref>{{cite web|last=Harrison|first=Paul|title=Robust topological sorting and Tarjan's algorithm in Python|url=http://www.logarithmic.net/pfh/blog/01208083168|accessdate = 9. 2. 2011.}}</ref>

== Reference ==
{{reflist}}

== Literatura ==
{{Литература}}
* {{citation|last1=Aspvall| first1 = Bengt|last2=Plass| first2 = Michael F.|authorlink3 = Robert Tarjan |last3=Tarjan| first3 = Robert E.|title = A linear-time algorithm for testing the truth of certain quantified boolean formulas
 | journal = Information Processing Letters
 | volume = 8 | issue = 3 |pages=121–123|year=1979
 | doi = 10.1016/0020-0190(79)90002-4}}.
* {{Cite book|author=Thomas H. Cormen |author2 = Charles E. Leiserson |author3 = Ronald L. Rivest |author4 = Clifford Stein|title=Introduction to Algorithms|location=|publisher=Second Edition. MIT Press and McGraw-Hill|year=2001|isbn=978-0-262-03293-3|pages=}} Section 22.5, pp. 552-557.}-
{{Литература крај}}
 
== Spoljašnje veze ==
* [http://www.ics.uci.edu/~eppstein/161/960220.html#sca Description of Tarjan's Algorithm]
* [http://stackoverflow.com/questions/6643076/tarjan-cycle-detection-help-c#sca Implementation of Tarjan's Algorithm in .NET]
* [https://github.com/danielrbradley/CycleDetection Implementation of Tarjan's Algorithm in .NET (GitHub)]
* [https://web.archive.org/web/20160315030747/http://www.vacilando.org/article/php-implementation-tarjans-cycle-detection-algorithm Implementation of Tarjan's Algorithm in PHP]
* [https://github.com/bwesterb/py-tarjan/ Another implementation of Tarjan's Algorithm in Python]
* [https://gist.github.com/1440602 Implementation of Tarjan's Algorithm in Javascript]
* [http://code.google.com/p/jbpt/ -{Java implementation for computation of strongly connected components] in the jBPT library (see StronglyConnectedComponents class)}-.

{{normativna kontrola}}

{{СОРТИРАЊЕ:Тарџанов алгоритам за налажење јако повезаних компоненти}}
[[Категорија:Графовски алгоритми]]