Back

ⓘ Tardžanov algoritam za nalaženje jako povezanih komponenti




Tardžanov algoritam za nalaženje jako povezanih komponenti
                                     

ⓘ Tardžanov algoritam za nalaženje jako povezanih komponenti

Tardžanov algoritam 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.

                                     

1. Pregled

Algoritam na ulazu dobija usmeren graf, 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 pronaden. 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 odredeno 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.

                                     

1.1. Pregled Svojstva korena

Srž algoritma je u odredivanju 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.

                                     

2. 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 strongconnectv end if repeat function strongconnectv // Postavlja index za v na najmanji neiskorisćeni index v.index:= index v.lowlink:= index index:= index + 1 S.pushv // 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 strongconnectw v.lowlink:= minv.lowlink, w.lowlink else if w is in S then // Sledbenik w je u steku S i stoga je u trenutnoj JPK v.lowlink:= minv.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 nadena 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 predeni. 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.



                                     

3. Primedbe

  • 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.
  • 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 | {\displaystyle O|V|+|E|}.
  • 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.
                                     

4. Spoljašnje veze

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

Users also searched:

...