Tarjanův algoritmus silně propojených komponent - Tarjans strongly connected components algorithm - Wikipedia

Tarjanův algoritmus silně propojených komponent

Tarjanova animace algoritmu
Datová struktura	Graf
Nejhorší případ výkon	${ displaystyle O (| V | + | E |)}$

Tarjanův algoritmus silně propojených komponent je algoritmus v teorie grafů pro nalezení silně připojené komponenty (SCC) společnosti a řízený graf. To běží dovnitř lineární čas, odpovídající časovému limitu pro alternativní metody včetně Kosarajuův algoritmus a algoritmus silné komponenty založený na cestě. Algoritmus je pojmenován pro jeho vynálezce, Robert Tarjan.^[1]

Přehled

Algoritmus trvá a řízený graf jako vstup a vytvoří a rozdělit grafů vrcholy do silně propojených komponent grafu. Každý vrchol grafu se objevuje přesně v jedné ze silně propojených komponent. Jakýkoli vrchol, který není v řízeném cyklu, tvoří sám o sobě silně spojenou komponentu: například vrchol, jehož vnitřní nebo vnější stupeň je 0, nebo jakýkoli vrchol acyklického grafu.

Základní myšlenka algoritmu je tato: hledání hloubky první (DFS) začíná od libovolného počátečního uzlu (a následné hledání hloubky první se provádí na všech uzlech, které dosud nebyly nalezeny). Jak je obvyklé u hloubkového vyhledávání, navštíví vyhledávání každý uzel grafu přesně jednou a odmítne znovu navštívit jakýkoli uzel, který již byl navštíven. Sbírka vyhledávacích stromů je tedy překlenující les grafu. Silně propojené komponenty budou obnoveny jako určité podstromy tohoto lesa. Kořeny těchto podstromů se nazývají „kořeny“ silně propojených komponent. Jakýkoli uzel silně propojené komponenty může sloužit jako root, pokud se stane prvním uzlem komponenty, který je objeven vyhledáváním.

Zásobník neměnný

Uzly jsou umístěny na a zásobník v pořadí, v jakém jsou navštíveny. Když vyhledávání hloubky první rekurzivně navštíví uzel proti a jeho potomci, tyto uzly nemusí být nutně vyskočeny ze zásobníku, když se vrátí toto rekurzivní volání. Rozhodující invariantní vlastnost je, že uzel zůstane na zásobníku poté, co byl navštíven, a to pouze tehdy, pokud ve vstupním grafu existuje cesta z něj do nějakého uzlu dříve v zásobníku. Jinými slovy to znamená, že v DFS by byl uzel odstraněn ze zásobníku teprve poté, co byly překonány všechny jeho připojené cesty. Když DFS ustoupí, odstranilo by uzly na jedné cestě a vrátilo se do kořenového adresáře, aby zahájilo novou cestu.

Na konci hovoru, který navštíví proti a jeho potomků, víme, zda proti sám má cestu k jakémukoli uzlu dříve v zásobníku. Pokud ano, hovor se vrátí a odejde proti na zásobníku, aby byla zachována invariantnost. Pokud ne, pak proti musí být kořenem jeho silně propojené komponenty, kterou tvoří proti společně s libovolnými uzly později v zásobníku než proti (tyto uzly mají všechny cesty zpět proti ale ne do žádného dřívějšího uzlu, protože kdyby měli cesty k dřívějším uzlům, pak proti by také měl cesty k dřívějším uzlům, což je nepravdivé). Připojená komponenta má kořeny v proti je poté vyskočeno ze zásobníku a vráceno, opět zachovávající invariant.

Vedení účetnictví

Každý uzel proti je přiřazeno jedinečné celé číslo v.index, který čísluje uzly postupně v pořadí, ve kterém jsou objeveny. Rovněž udržuje hodnotu v.lowlink který představuje nejmenší index kteréhokoli uzlu, o kterém je známo, že je dosažitelný proti přes protipodstrom DFS, včetně proti sám. Proto proti musí být ponechán na zásobníku, pokud v.lowlink , zatímco v musí být odstraněno jako kořen silně připojené komponenty, pokud v.lowlink == v.index. Hodnota v.lowlink se počítá během hloubkového vyhledávání od proti, protože to najde uzly, ze kterých je dosažitelný proti.

Algoritmus v pseudokódu

algoritmus tarjan je    vstup: graf G = (PROTI, E)    výstup: sada silně propojených komponent (sady vrcholů) index := 0    S : = prázdný zásobník pro každého proti v PROTI dělat        -li proti.index není definován pak            strongconnect (proti)        skončit, pokud    konec pro       funkce strongconnect (proti)        // Nastavte hloubkový index pro v na nejmenší nevyužitý index        proti.index: = index        proti.lowlink: = index        index := index + 1        S.tlačit(proti)        proti.onStack: = true // Zvažte nástupce v        pro každého (proti, w) v E dělat            -li w.index není definován pak                // Nástupce w ještě nebyl navštíven; opakovat na to                strongconnect (w)                proti.lowlink: = min (proti.lowlink, w.lowlink) jinak pokud w.onStack pak                // Nástupce w je v zásobníku S, a tedy v aktuálním SCC                // Pokud w není na zásobníku, pak (proti, w) je hrana směřující k již nalezenému SCC a musí být ignorována                // Poznámka: Následující řádek může vypadat divně - ale je správný.                // Říká se, že w.index není w.lowlink; to je záměrné az původního papíru                proti.lowlink: = min (proti.lowlink, w.index) skončit, pokud        konec pro              // Pokud v je kořenový uzel, vysuňte zásobník a vygenerujte SCC        -li proti.lowlink = proti.index pak            spustit novou silně připojenou komponentu opakovat                w := S.pop () w.onStack: = false add w na silně připojenou součást zatímco w ≠ proti            výstup aktuální silně připojené komponenty skončit, pokud    koncová funkce

The index proměnná je počitadlo počtu vyhledávacích uzlů první hloubky. S je zásobník uzlů, který začíná prázdný a ukládá historii prozkoumaných uzlů, které ještě nebyly přiděleny silně připojené součásti. Všimněte si, že se nejedná o normální vyhledávací zásobník s hloubkou první, protože uzly se nevyskakují, protože vyhledávání se vrací do stromu; zobrazí se pouze v případě, že byla nalezena celá silně připojená součást.

Nejvzdálenější smyčka prohledá každý uzel, který ještě nebyl navštíven, a zajistí, že uzly, které nejsou dosažitelné z prvního uzlu, budou nakonec nakonec překonány. Funkce silné připojení provede jediné hloubkové prohledání grafu a vyhledá všechny nástupce z uzlu protia hlášení všech silně propojených komponent tohoto podgrafu.

Když každý uzel dokončí opakování, pokud je jeho nízký odkaz stále nastaven na svůj index, pak je to kořenový uzel silně propojené komponenty, tvořený všemi uzly nad ním v zásobníku. Algoritmus vyskakuje zásobník až k aktuálnímu uzlu včetně a zobrazuje všechny tyto uzly jako silně propojenou součást.

Všimněte si, že proti.lowlink: = min (proti.lowlink, w.index) je správný způsob aktualizace v.lowlink -li w je na zásobníku. Protože w je již v zásobníku, (v, w) je back-edge ve stromu DFS, a proto w není v podstromu proti. Protože v.lowlink bere v úvahu uzly dosažitelné pouze přes uzly v podstromu proti musíme se zastavit w a použít w.index namísto w.lowlink.

Složitost

Časová složitost: Tarjanova procedura je volána jednou pro každý uzel; prohlášení forall zohledňuje každou hranu maximálně jednou. Doba chodu algoritmu je proto lineární v počtu hran a uzlů v G, tj. ${ displaystyle O (| V | + | E |)}$.

Aby bylo možné dosáhnout této složitosti, proveďte test, zda w je na zásobníku by mělo být provedeno v konstantním čase. To lze provést například uložením příznaku na každém uzlu, který označuje, zda je na zásobníku, a provedením tohoto testu zkoumáním příznaku.

Složitost vesmíru: Tarjanův postup vyžaduje pro slovo dvě slova doplňujících údajů na vrchol index a lowlink pole, spolu s jedním bitem pro onStack a další pro určení, kdy index není definováno. Kromě toho je na každém rámci stohu nutné držet jedno slovo proti a další pro aktuální pozici v seznamu hran. Konečně nejhorší velikost zásobníku S musí být ${ displaystyle | V |}$ (tj. když je graf jednou obří složkou). Toto poskytuje konečnou analýzu ${ displaystyle O (| V | cdot (2 + 5w))}$ kde ${ displaystyle w}$ je velikost slova stroje. Variace Nuutily a Soisalon-Soininenu to snížila na ${ displaystyle O (| V | cdot (1 + 4w))}$ a následně to vyžaduje pouze Pearce ${ displaystyle O (| V | cdot (1 + 3w))}$.[2][3]

Další poznámky

I když na pořadí uzlů v každé silně propojené komponentě není nic zvláštního, jednou z užitečných vlastností algoritmu je, že před žádným z jejích nástupců nebude identifikována žádná silně připojená komponenta. Pořadí, ve kterém jsou silně propojené komponenty identifikovány, tedy představuje obrácené pořadí topologické třídění z DAG tvořené silně propojenými součástmi.[4]

Donald Knuth popsal Tarjanův SCC algoritmus jako jednu ze svých oblíbených implementací v knize Stanford GraphBase.[5]

Také napsal:[6]

Datové struktury, které pro tento problém vymyslel, do sebe zapadají neuvěřitelně krásným způsobem, takže množství, na která se musíte dívat při zkoumání směrovaného grafu, máte vždy kouzelně na dosah ruky. A jeho algoritmus také provádí topologické třídění jako vedlejší produkt.

Reference