Tarjanův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 14. června 2022; kontroly vyžadují 5 úprav .

Tarjanův algoritmus  je algoritmus pro nalezení silně propojených složek v digrafu , který běží v lineárním čase.


Tento algoritmus je založen na:

  1. Vrcholy jsou uvažovány v obráceném topologickém pořadí, takže na konci rekurzivní funkce pro původní vrchol nenarazíme na žádný vrchol ze stejné silně propojené komponenty, protože všechny vrcholy dosažitelné z původního vrcholu již byly zpracovány.
  2. Zpětné vazby ve stromu poskytují druhou cestu z jednoho vrcholu do druhého a spojují silně propojené komponenty do jedné.

Neformální popis algoritmu

Tarjanův algoritmus lze chápat jako variaci algoritmu prohledávání do hloubky , ve kterém se při návštěvě uzlu provádějí další kroky a je dokončeno zpracování uzlu. K návštěvě vrcholu dochází při přechodu od kořene k listům a ukončení zpracování vrcholu nastává na cestě zpět. Při návštěvě vrcholu se odsune do pomocného zásobníku, při zpracování silně propojené komponenty jsou všechny jeho vrcholy vytlačeny z tohoto zásobníku [1] .

Algoritmus v pseudokódu

// vstupní data: orientovaný graf G = (V, A) // výstupní data: sada silně propojených komponent index  := 0 zásobník  := [] pro každé v ve V do if v .index = null then strongconnect( v ) funkce strongconnect( v ) // V indexu ukládáme počet dříve zpracovaných vrcholů, v.index je "čas vstupu" do vrcholu v v .index := index v .lowlink := index index  := index + 1 zásobník .push( v ) // Pole onStack je potřeba ke kontrole, zda vrchol patří do zásobníku v O(1) v .onStack := true // Iterace přes oblouky odcházející z v pro každý ( v , w ) v A do if w .index = null then // Vrchol w nebyl předtím navštíven; spustit rekurzivně z něj strongconnect( w ) v .lowlink := min( v .lowlink, w .lowlink) jinak if w .onStack then // Vertex w je na zásobníku, takže patří do stejné silně propojené komponenty jako v / / Pokud w není na zásobníku, pak oblouk ( v , w ) vede k dříve zpracované silně připojené komponentě a měl by být ignorován // Poznámka: další řádek záměrně používá w.index místo w.lowlink - to se týká Tarjanův původní článek / / Pokud nahradíme w.index za w.lowlink, algoritmus zůstane správný v .lowlink := min( v .lowlink, w .index ) // Vertex v je kořen aktuální silně propojené komponenty, všechny vrcholy v zásobníku od v a výše tvoří tuto komponentu , pokud v .lowlink = v .index then vytvořit novou silně propojenou komponentu repeat w  := stack .pop() w .onStack := false přidejte w k aktuální silně připojené složce , zatímco w ≠ v výstup aktuální silně připojené součásti

Otevírací doba

Algoritmus má časovou složitost , kde  je počet oblouků a  jsou vrcholy grafu [1] .

Viz také

Silně propojený algoritmus hledání komponent se dvěma zásobníky  je podobný algoritmus, který používá prohledávání do hloubky.

Poznámky

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

Odkazy

Literatura