Algoritmul lui Tarjan

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 14 iunie 2022; verificările necesită 5 modificări .

Algoritmul lui Tarjan  este un algoritm pentru găsirea componentelor puternic conectate într-un digraf care rulează în timp liniar.


Acest algoritm se bazează pe:

  1. Vârfurile sunt considerate în ordine topologică inversă, astfel încât la sfârșitul funcției recursive pentru vârful inițial, nu va fi întâlnit niciun vârf din aceeași componentă puternic conectată, deoarece toate vârfurile accesibile de la vârful original au fost deja procesate.
  2. Feedback-urile dintr-un arbore oferă o a doua cale de la un vârf la altul și conectează componentele puternic conectate într-una singură.

Descrierea informală a algoritmului

Algoritmul lui Tarjan poate fi înțeles ca o variație a algoritmului de căutare în profunzime , în care se efectuează pași suplimentari atunci când un nod este vizitat și procesarea nodului este finalizată. O vizită la un vârf are loc atunci când se trece de la rădăcină la frunze, iar sfârșitul procesării vârfului are loc la întoarcere. Când un vârf este vizitat, acesta este împins în stiva auxiliară; atunci când o componentă puternic conectată este procesată, toate vârfurile sale sunt împinse din această stivă [1] .

Algoritm în pseudocod

// date de intrare: grafic direcționat G = (V, A) // date de ieșire: set de componente puternic conectate index  := 0 stivă  := [] pentru fiecare v din V face dacă v .index = null atunci strongconnect( v ) function strongconnect( v ) // În index stocăm numărul de vârfuri procesate anterior, v.index este „timpul de intrare” la vârf v v .index := index v .lowlink := index index  := index + 1 stivă .push( v ) // Câmpul onStack este necesar pentru a verifica dacă partea de sus aparține stivei din O(1) v .onStack := true // Iterează peste arcele care ies din v pentru fiecare ( v , w ) în A do if w .index = null atunci // Vârful w nu a fost vizitat înainte; rulați recursiv din el strongconnect( w ) v .lowlink := min( v .lowlink, w .lowlink) altfel dacă w .onStack atunci // Vertex w este pe stivă, deci aparține aceleiași componente puternic conectate ca v / / Dacă w nu este pe stivă, atunci arcul ( v , w ) duce la componenta puternic conectată procesată anterior și ar trebui ignorată // Notă: următoarea linie folosește în mod deliberat w.index în loc de w.lowlink - aceasta se referă la Articolul original al lui Tarjan / / Dacă înlocuim w.index cu w.lowlink, algoritmul rămâne corect v .lowlink := min( v .lowlink, w .index) // Vârful v este rădăcina componentei curente puternic conectate, toate vârfurile din stiva de la v și mai sus formează această componentă dacă v .lowlink = v .index atunci creați o nouă componentă puternic conectată repetă w  := stivă .pop() w .onStack := fals adăugați w la componenta curentă puternic conectată în timp ce w ≠ v scoateți componenta curentă puternic conectată

Orele de deschidere

Algoritmul are complexitate în timp , unde  este numărul de arce și  sunt vârfurile graficului [1] .

Vezi și

Algoritmul de căutare a componentelor Strongly Connected Two-Stack  este un algoritm similar care utilizează căutarea în profunzime.

Note

  1. ↑ 1 2 Jeremy Sik et al., 2006 .

Link -uri

Literatură