Kosarayu algoritmusa

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. október 25-én felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

Kosaraju algoritmusa (az indiai származású amerikai tudós, Sambasiva Rao Kosaraju tiszteletére) egy algoritmus az erősen összefüggő régiók megtalálására egy irányított gráfban . Az erős összeköttetésű területek megtalálásához a mélységi keresést (DFS) először az eredeti gráf megfordításán (vagyis az ívekkel szemben) hajtják végre, kiszámítva a csúcsokból a kilépési sorrendet. Ezután ezzel a sorrend-inverzióval végezzünk mélységi keresést az eredeti gráfon (ismét a visszafelé haladás során kapott maximális számú csúcsot vesszük fel). A DFS-erdő ennek eredményeként kiválasztott fái erős összetevők.

Definíciók

Az irányított aciklikus gráf  olyan irányított gráf, amely nem tartalmaz irányított ciklusokat.

Algoritmus

  1. Megfordítjuk az eredeti irányított gráf íveit.
  2. Mélység-első keresést futtatunk ezen az invertált gráfon, emlékezve arra, hogy milyen sorrendben léptünk ki a csúcsokból.
  3. Elindítunk egy mélységi keresést az eredeti gráfon, ismét kiválasztva a 2. lépésben kapott vektorban a maximális számú meg nem látogatott csúcsot.
  4. A fák a 3. pontból származnak, és szorosan összefüggő összetevők.

Ingatlan

A Kosaraju módszer egy gráf erősen összefüggő összetevőinek keresését teszi lehetővé lineáris időben és memóriában.

Bizonyítás: Ez a módszer két mélységben-először-először-először-először-először-először-először-először-először-először-először-először-először-először-először-először-először-készlet-rutinból áll, kisebb módosításokkal, hogy a futási ideje telített gráfok esetén arányos V²-vel, ritka gráfok esetén pedig V + E-vel (ha a gráfokat szomszédos csúcsok listájaként ábrázoljuk).

Példa

Az alábbiakban egy példa látható a Kosaraju algoritmus működésére.

Egy balra lent irányított gráf erős összetevőinek kiszámításához először mélységi keresést végzünk a hátoldalán (bal felső sarokban), kiszámítva az inverz bejárási sorrendvektort (Order). Ez a sorrend megegyezik a DFS-erdő bejárásának fordított sorrendjével. Ennek a sorrendnek az inverzióját használva mélységi bejárást végzünk az eredeti gráfon. Vagyis a 3. csomópontnál kezdjük. A folyamat eredményeként kiválasztott DFS-erdő fái erős összetevők. Az id vektor tartalma a komponens száma, a bal oldali számok a csúcs száma.

Linkek

Irodalom