Tarjan erősen összefüggő komponensek algoritmusa

Tarjan erősen összefüggő komponensek algoritmusa
Legrosszabb időbonyolultság	$O(|V|+|E|)$

A Tarjan erősen összefüggő komponensek algoritmusa egy gráfelméleti algoritmus, amely egy irányított gráf erősen összefüggő komponenseinek (SCC) megtalálására szolgál. Lineáris idő alatt fut, és megfelel az alternatív módszerek, köztük a Kosaraju-algoritmus és az útvonalalapú erős komponens algoritmus időhatárainak. Az algoritmus a feltalálójáról, Robert Tarjanról kapta a nevét.

Áttekintés

Az algoritmus bemenetként egy irányított gráfot fogad el, és létrehozza a gráf csúcsainak felosztását a gráf erősen összefüggő komponenseire. A gráf minden egyes csúcsa pontosan az erősen összefüggő komponensek egyikében jelenik meg. Minden olyan csúcs, amely nem egy irányított ciklusban van, önmagában is erősen összefüggő komponenst alkot: például egy olyan csúcs, amelynek a bel- vagy kültagja 0, vagy egy aciklikus gráf bármelyik csúcsa.

Az algoritmus alapgondolata a következő: a mélységi keresés egy tetszőleges kezdőcsomópontból indul (és a későbbi mélységi keresések minden olyan csomóponton folynak, amelyet még nem találtak meg). A mélységi keresésnél szokásos módon a keresés a gráf minden csomópontját pontosan egyszer keresi fel, és nem látogat meg újra olyan csomópontot, amelyet már meglátogatott. Így a keresési fák gyűjteménye a gráf egy átfutó erdője. Az erősen összefüggő komponensek ennek az erdőnek bizonyos részfáiként lesznek visszanyerhetők. Ezeknek a részfáknak a gyökereit nevezzük az erősen összefüggő komponensek „gyökereinek”. Egy erősen összefüggő komponens bármelyik csomópontja szolgálhat gyökérként, ha történetesen ez a keresés által felfedezett komponens első csomópontja.

Verem invariáns

A csomópontok a látogatás sorrendjében kerülnek a verembe. Amikor a mélységi keresés rekurzív módon meglátogat egy v csomópontot és annak leszármazottait, akkor ezek a csomópontok nem feltétlenül kerülnek ki a veremből, amikor a rekurzív hívás visszatér. A legfőbb invariáns tulajdonság az, hogy egy csomópont akkor és csak akkor marad a veremben, miután meglátogattuk, ha a bemeneti gráfban létezik egy út a csomópontból a verem egy korábbi csomópontjához. Más szóval ez azt jelenti, hogy a mélységi keresésből származó csomópont csak akkor kerül le a veremből, ha az összes kapcsolódó útvonalát bejárta. Amikor a mélységi keresés visszalép, akkor eltávolítja az egyetlen útvonalon lévő csomópontokat, és visszatér a gyökérhez, hogy új útvonalat kezdjen.

A v és leszármazottait meglátogató hívás végén tudjuk, hogy v-nek van-e útja a verem bármely korábbi csomópontjához. Ha igen, akkor a hívás visszatér, v-t a veremben hagyva az invariáns megőrzése érdekében. Ha nem, akkor v a gyökere kell, hogy legyen az erősen összefüggő komponensének, amely v-ből és a v-nél későbbi csomópontokból áll (ezek a csomópontok mind visszavezetnek v-hez, de nem vezetnek vissza korábbi csomópontokhoz, mert ha lenne útjuk korábbi csomópontokhoz, akkor v-nek is lenne útja korábbi csomópontokhoz, ami hamis). A v-ben gyökerező összefüggő komponens ezután lekerül a veremről és visszakerül, ismét az invariáns megőrzésével.

Könyvelés

Minden egyes v csomóponthoz egy egyedi v.index-et (integer) rendelünk, amely a csomópontokat a felfedezésük sorrendjében sorszámozza. A rendszer nyilvántart egy v.lowlink értéket, amely a legkisebb indexét reprezentálja bármelyik csomópontnak, melyről tudott hogy elérhetőv-n vagy annak mélység-első keresésből származó részfáján keresztül. Ezért v-t a veremben kell hagyni, ha v.lowlink < v.index, míg v-t mint egy erősen összefüggő komponens gyökerét el kell távolítani, ha v.lowlink == v.index. A v.lowlink értékét a v-ből kiinduló mélységi keresés során számítjuk ki, mivel ez találja meg a v-ből elérhető csomópontokat.

Vegyük észre, hogy a lowlink különbözik a lowpoint-tól, amely a legkisebb olyan index, amely v-ből a gráf bármely részén keresztül elérhető.

Az algoritmus pszeudokódja (angol)

algorithm tarjan is
    input: graph G = (V, E)
    output: set of strongly connected components (sets of vertices)
   
    index := 0
    S := empty stack
    for each v in V do
        if v.index is undefined then
            strongconnect(v)
        end if
    end for
   
    function strongconnect(v)
        // Set the depth index for v to the smallest unused index
        v.index := index
        v.lowlink := index
        index := index + 1
        S.push(v)
        v.onStack := true
      
        // Consider successors of v
        for each (v, w) in E do
            if w.index is undefined then
                // Successor w has not yet been visited; recurse on it
                strongconnect(w)
                v.lowlink := min(v.lowlink, w.lowlink)
            else if w.onStack then
                // Successor w is in stack S and hence in the current SCC
                // If w is not on stack, then (v, w) is an edge pointing to an SCC already found and must be ignored
                // Note: The next line may look odd - but is correct.
                // It says w.index not w.lowlink; that is deliberate and from the original paper
                v.lowlink := min(v.lowlink, w.index)
            end if
        end for
      
        // If v is a root node, pop the stack and generate an SCC
        if v.lowlink = v.index then
            start a new strongly connected component
            repeat
                w := S.pop()
                w.onStack := false
                add w to current strongly connected component
            while w ≠ v
            output the current strongly connected component
        end if
    end function

Az index változó a mélységi keresési csomópontok számának számlálója. S a csomóponthalom, amely üresen indul, és a feltárt, de még nem erősen összefüggő komponenshez kötött csomópontok előzményeit tárolja. Vegyük észre, hogy ez nem a szokásos mélység-első keresési verem, mivel a csomópontok nem kerülnek ki belőle, amikor a keresés a fán felfelé halad; csak akkor kerülnek ki, amikor egy teljes, erősen összefüggő komponenst találtunk.

A legkülső hurok minden olyan csomópontot átnéz, amelyet még nem látogattunk meg, biztosítva ezzel azt, hogy az első csomópontból nem elérhető csomópontokat végül mégis bejárjuk. A strongconnect függvény egyetlen mélységi keresést végez a gráfban, megkeresi a v, csomópont összes utódját, és jelenti az adott részgráf összes erősen összefüggő komponensét.

Amikor minden egyes csomópont befejezi az átfutást, ha a lowlinkje még mindig az indexére van állítva, akkor az a csomópont egy erősen összefüggő komponens gyökércsomópontja, amelyet a veremben felette lévő összes csomópont alkot. Az algoritmus az aktuális csomópontig bezárólag feltölti a vermet, és az összes ilyen csomópontot erősen összefüggő komponensként mutatja be.

Vegyük észre, hogy v.lowlink := min(v.lowlink, w.index) a helyes módja a v.lowlink frissítésének, ha w a veremben van. Mivel w már a veremben van, ezért(v, w) egy hátsó él a mélység-első kereső fájában, ezért w nincs v.részfájában. Mert v.lowlink csak a v részfájában lévő csomópontokon keresztül elérhető csomópontokat veszi figyelembe, meg kell állnunk w és a w.index-et kell használnunk a w.lowlink helyett.

Komplexitás

Időbeli komplexitás: A forall utasítás minden egyes élt legfeljebb egyszer vesz figyelembe. Az algoritmus futási ideje ezért lineáris a G éleinek és csomópontjainak számával, azaz$O(|V|+|E|)$.

Ahhoz, hogy ezt a komplexitást elérjük, a w halmazon való elhelyezkedésének vizsgálatát konstans idő alatt kell elvégezni. Ez megoldható például úgy, hogy minden csomóponton tárolunk egy flag-et, amely jelzi, hogy az adott csomópont a veremben van-e, és ezt a tesztet a flag vizsgálatával végezzük el.

Térkomplexitás: A Tarjan-eljárás csúcsonként két szó kiegészítő adatot igényel az index és alowlink mezőkhöz, valamint egy bitet az onStack-hez és egy másikat annak meghatározásához, hogy az index nem definiált. Ezenkívül minden egyes veremkeretben egy szóra van szükség a v tárolásához, és egy másik szóra az élek listájának aktuális pozíciójához.

Végül, az S verem legrosszabb esetben mért mérete $|V|$ lehet (azaz amikor a gráf egyetlen óriás komponens). Ez adja a következő végső elemzést $O(|V|\cdot (2+5w))$ ahol $w$ a gépi szóméret. Nuutila és Soisalon-Soininen variációja ezt a következőre csökkentette $O(|V|\cdot (1+4w))$ és ezt követően Pearce-é csak ennyit igényel $O(|V|\cdot (1+3w))$.

További megjegyzések

Bár az egyes erősen összefüggő komponenseken belüli csomópontok sorrendje nem különleges, az algoritmus egyik hasznos tulajdonsága, hogy egyetlen erősen összefüggő komponens sem lesz előbb azonosítva, mint bármelyik utódja. Ezért az erősen összefüggő komponensek azonosításának sorrendje az erősen összefüggő komponensek által alkotott közvetlenül aciklikus gráf (DAG) fordított topologikus sorrendjét jelenti.

Donald Knuth a The Stanford GraphBase című könyvében Tarjan SCC algoritmusát egyik kedvenc implementációjaként írta le. Ezt is ő írta:

„Az adatszerkezetek, amelyeket erre a problémára talált ki, elképesztően szépen illeszkednek egymáshoz, így azok a mennyiségek, amelyeket egy irányított gráf felfedezése során meg kell néznünk, varázslatos módon mindig kéznél vannak. És az algoritmusa melléktermékként topológiai rendezést is végez.”

Fordítás

• Ez a szócikk részben vagy egészben a Tarjan's strongly connected components algorithm című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

• Rosetta Code, az algoritmus implementációja különféle programozási nyelveken