Tardžanov algoritam za nalaženje jako povezanih komponenti
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 
 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. .
 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.

Reference

Literatura 

 .
  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)}-.

Графовски алгоритми
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 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 . \ . 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 . Reference Literatura \ . Section5 , pp. }- 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 ) }- . Графовски алгоритми