Kosaraju-algoritmus

Kosaraju-algoritmus
Legrosszabb időbonyolultság	$O({|V|}^{2})$ $\Theta (|V|+|E|)$

A számítástechnikában a Kosaraju–Sharir-algoritmus vagy Kosaraju algoritmusa lineáris idejű algoritmus egy irányított gráf erősen összefüggő komponenseinek megtalálására. Aho, Hopcroft, Ullman S. Rao Kosaraju és Micha Sharir nevéhez fűződik. Kosaraju 1978-ban állt elő az ötlettel, de nem publikálta, míg Sharir ettől függetlenül fedezte fel és 1981-ben publikálta. Az algoritmus kihasználja azt a tényt, hogy a transzponált gráf (ugyanaz a gráf, de minden él iránya megfordul) pontosan ugyanazokkal a szorosan összefüggő komponensekkel rendelkezik, mint az eredeti gráf.

Az algoritmus

Az algoritmus által használt primitív gráfműveletek a következők:

• a gráf csúcsainak felsorolása,
• az adatok tárolása csúcsonként (ha nem magában a gráf adatstruktúrájában, akkor valamilyen táblázatban, amely a csúcsokat indexként használhatja),
• egy csúcs külső szomszédainak felsorolása (élek átjárása előrefelé),
• egy csúcs belső szomszédainak felsorolása (élek átjárása visszafelé);

ez utóbbi azonban elvégezhető anélkül is, de az előremenő átjárási fázis során meg kell építeni a transzponált gráf reprezentációját. Az algoritmus egyetlen további adatszerkezete a gráf csúcsainak rendezett L listája, amely minden egyes csúcsot egyszer tartalmaz.

Ha az erős komponenseket úgy kell ábrázolni, hogy minden komponensnek külön gyökércsúcsot jelölünk ki, és minden egyes csúcshoz hozzárendeljük a komponens gyökércsúcsát, akkor Kosaraju algoritmusa a következőképpen fogalmazható meg:

1. A gráf minden u csúcsát jelöljük meg nem látogatottnak. L legyen üres.
2. A gráf minden u csúcsára alkalmazzuk a Visit(u) rekurzív függvényt/eljárást, ahol Visit(u):

   Ha u még nem látogatott, akkor:

   1. Jelöljük u-t látogatottnak.
   2. Az u minden egyes v szomszédjára, ha az még nem látogatott, alkalmazzuk Visit(v)-t.
   3. Tegyük u-t az L-be.

   Különben ne csináljon semmit.

3. Az L minden egyes u elemére sorrendben alkalmazzuk el az Assign(u,root) műveletet, ahol az Assign(u,root) a következőképp írható le:

   Ha u nem lett hozzárendelve egy komponenshez, akkor:

   1. hozzárendeljük u-t ahhoz az összetevőhöz tartozónak, amelynek a gyökere a root.
   2. Az u minden egyes v szomszédos komponensére hívjuk meg az Assign(v,root) parancsot.

   Különben ne csináljon semmit.

Triviális variáció, hogy ehelyett minden egyes csúcshoz komponensszámot rendelünk, vagy komponensenként listákat készítünk a hozzá tartozó csúcsokról. A nem látogatott/látogatott jelzést tárolhatjuk a tárolási helyen a csúcsok gyökerének végleges hozzárendelésével.

Az algoritmus lényege, hogy a gráf éleinek első (előremenő) bejárása során a csúcsok a feltárandó keresési fához viszonyított fordított sorrendben kerülnek az L listába. Ez azt jelenti, hogy nem számít, hogy egy v csúcsot azért látogattunk meg először, mert az összes csúcs felsorolásában szerepelt, vagy mert egy másik meglátogatott u csúcs külső szomszédja volt; mindkét esetben v előbb kerül be az L-be, mint u, így, ha van egy előre vezető út u-tól v-ig, akkor u előbb fog megjelenni a végső L listán, mint v (kivéve, ha u és v ugyanahhoz az erős komponenshez tartozik, amely esetben a relatív sorrendjük az L-ben tetszőleges).

Ez azt jelenti, hogy a lista minden egyest $n$ eleme megfeleltethető egy $L[i_{n-1}:i_{n}]$ blokknak, ahol a blokk az összes olyan csúcsból áll, amely az $n$ csúcsból elérhető, csak az útvonal minden egyes csomópontjánál kifelé irányuló élekkel. Fontos megjegyezni, hogy az n-nel kezdődő blokkban egyetlen csúcsnak sincs befelé irányuló kapcsolata a tőle jobbra lévő valamelyik csúcsból kezdődő blokkokból, azaz a listában szereplő $i_{n},i_{n}+1,...N$ csúcsoknak megfelelő blokkokbólt. Ennek az oka, mert különben a befelé irányuló kapcsolattal rendelkező csúcsot (mondjuk az $n'\geq i_{n}+1$ blokkból kiindulva) már meglátogattuk volna és előzetesen az L blokkban $n'$-be helyeztük volna, ami ellentmondás. Másrészt, az $n$-ben kezdődő blokkban lévő csúcsok élei $\{i_{n},i_{n}+1,...N\}$ valamelyik csúcsával kezdődő blokkokra mutathatnak.

Az algoritmus 3. lépése az $L[0]$-ból indul, és minden olyan csúcshoz, amely erre mutat, ugyanazt a komponenst rendeli hozzá, mint $L[0]$. Vegyük észre, hogy ezek a csúcsok csak az $L[0]$] kezdetű blokkban lehetnek, mivel magasabb blokkokban nem lehetnek olyan kapcsolatok, amelyek az $L[0]$ blokkban lévő csúcsokra mutatnak. Legyen az $L[0]$-ra mutató összes csúcs halmaza $In(L[0])$. Ezt követően az összes olyan csúcsot, amely ezekre a csúcsokra mutat, $In(In(L[0]))$ szintén hozzáadjuk, és így tovább, amíg több csúcsot nem tudunk hozzáadni.

Az $L[0]$-t tartalmazó komponenshez hozzáadott összes csúcsból van egy út az $L[0]$-hoz. És van egy út az $L[0]$-ból hozzáadott összes csúcshoz, mivel azok mind az $L[0]$-val kezdődő blokkban vannak (amely tartalmazza az összes olyan csúcsot, amely az $L[0]$-ból elérhető, az út minden lépésénél kifelé irányuló élek mentén. Ezek tehát mind egyetlen erősen összefüggő komponenst alkotnak. Ráadásul egyetlen csúcs sem marad, mert ahhoz, hogy egy csúcs ebben az erősen összefüggő komponensben legyen, el kell érnie ${\displaystyle L[0]}$-ból, és el kell tudnia érnie ${\displaystyle L[0]}$-t. Minden olyan csúcs, amely képes elérni ${\displaystyle L[0]}$, ha van ilyen, csak az első blokkban van, és az első blokkban lévő összes csúcs elérhető $L[0]$-ból. Az algoritmus tehát az ${\displaystyle L[0]}$ összefüggő komponensének minden csúcsát kiválasztja.

Amikor a 3. lépés ciklusában elérjük a $v=L[i]$ csúcsot, és $v$ nem lett hozzárendelve egyetlen komponenshez sem, biztosak lehetünk benne, hogy a tőle balra lévő összes csúcs meghatározta az összefüggő komponenseit; hogy $v$ nem tartozik egyik komponenshez sem; hogy $v$ nem mutat a tőle balra lévő csúcsok egyikére sem. Továbbá, mivel a magasabb blokkokból nincs él a $v$ blokkjába, a bizonyítás ugyanaz marad.

A fentiek szerint az algoritmus az egyszerűség kedvéért mélységi keresést alkalmaz, de ugyanúgy használhatna szélességi keresést is, amíg a sorrend utáni tulajdonság megmarad.

Az algoritmus úgy értelmezhető, hogy egy $u$ csúcs erős komponensét azon csúcsok halmazaként azonosítjuk, amelyek $u$-ból mind visszafelé, mind előrefelé haladva elérhetőek. Az algoritmus 2. fázisa után az algoritmus 2. fázisa után az L listán szigorúan u előtt megjelenő csúcsok halmazá $F(u)$-ból az $u$-bólelőrefelé történő átjárással elérhető csúcsok halmaza, $B(u)$ az $u$-ból visszafelé történő átjárással elérhető csúcsok halmaza, és $P(u)$ az algoritmus 2. fázisa után az $u$-t gyökérnek nevezett csúcsot tartalmazó erős komponens a következő

$B(u)\cap F(u)=B(u)\setminus (B(u)\setminus F(u))=B(u)\setminus P(u)$.

A halmazok metszése számításigényes, de logikailag egyenértékű a kettős halmazkülönbséggel, és mivel $B(u)\setminus F(u)\subseteq P(u)$, elegendő tesztelni, hogy a $B(u)$ egy újonnan előkerült eleme már hozzárendelődött-e valamelyik komponenshez vagy sem.

Komplexitás

Feltéve, hogy a gráfot szomszédsági-listával írjuk le, Kosaraju algoritmusa két teljes átjárást végez a gráfon és így Θ(V+E) (lineáris) idő alatt fut, ami aszimptotikusan optimális, mivel van egy megfelelő alsó korlát (bármely algoritmusnak minden csúcsot és élt meg kell vizsgálnia). Ez a koncepcionálisan legegyszerűbb hatékony algoritmus, de a gyakorlatban nem olyan hatékony, mint Tarjan erősen összefüggő komponensek algoritmusa és az út alapú erős komponensek algoritmusa, amelyek csak egy átjárást végeznek a gráfon.

Ha a gráf szomszédsági mátrixként van ábrázolva, az algoritmus Ο(V²) időt igényel.

Fordítás

• Ez a szócikk részben vagy egészben a Kosaraju's 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.

Források

• Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1983.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 3rd edition. The MIT Press, 2009. ISBN 0-262-03384-4.
• Micha Sharir. A strong-connectivity algorithm and its applications to data flow analysis. Computers and Mathematics with Applications 7(1):67–72, 1981.