Tarján 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 2022. június 14-én felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A Tarjan-féle algoritmus egy lineáris időben futó digráfban erősen összefüggő komponensek  megtalálására szolgáló algoritmus .


Ez az algoritmus a következőkön alapul:

  1. A csúcsok fordított topológiai sorrendben kerülnek figyelembevételre, így az eredeti csúcs rekurzív függvényének végén nem fog találkozni ugyanabból az erősen kapcsolódó komponensből származó csúcsokkal, mivel az eredeti csúcsból elérhető összes csúcsot már feldolgozták.
  2. A fában lévő visszacsatolások egy második utat adnak az egyik csúcsból a másikba, és összekapcsolják az erősen kapcsolódó összetevőket.

Az algoritmus informális leírása

Tarjan algoritmusa felfogható a mélységi keresési algoritmus egy változataként , amelyben további lépések végrehajtására kerül sor, amikor egy csomópontot meglátogatnak és a csomópont feldolgozása befejeződik. A csúcs meglátogatása a gyökértől a levelek felé haladva történik, és a csúcs feldolgozása a visszaúton következik be. Amikor egy csúcsot meglátogatunk, az a segédverembe kerül, egy erősen kapcsolódó komponens feldolgozása során pedig az összes csúcsa kiszorul ebből a veremből [1] .

Algoritmus pszeudokódban

// bemeneti adatok: irányított gráf G = (V, A) // kimeneti adatok: erősen kapcsolódó komponensek halmaza index  := 0 verem  := [] minden v - hez V do ha v .index = null then strongconnect( v ) function strongconnect( v ) // Az indexben a korábban feldolgozott csúcsok számát tároljuk, a v.index a csúcsba való "belépési idő" v v .index := index v .lowlink := index index  := index + 1 verem .push( v ) // Az onStack mezőre annak ellenőrzésére van szükség, hogy a teteje az O(1) v .onStack := vereméhez tartozik-e // Iterálás a v -ből kimenő íveken minden ( v , w ) esetén A do -ban, ha w .index = null then // A w csúcsot még nem látogatták meg; rekurzívan fut belőle strongconnect( w ) v .lowlink := min( v .lowlink, w .lowlink) else if w .onStack then // A w csúcs a veremen van, tehát ugyanahhoz az erősen kapcsolódó komponenshez tartozik, mint a v / / Ha w nincs a veremben, akkor az ív ( v , w ) az előzőleg feldolgozott erősen kapcsolt komponenshez vezet, és figyelmen kívül kell hagyni // Megjegyzés: a következő sorban a w.lowlink helyett szándékosan a w.index szerepel - ez arra vonatkozik, Tarján eredeti cikke / / Ha a w.index-et w.lowlink-re cseréljük, akkor az algoritmus helyes marad v .lowlink := min( v .lowlink, w .index) // A v csúcs az aktuális erősen kapcsolódó komponens gyökere, a veremben lévő összes csúcs a v-től és a fentiektől ezt a komponenst alkotja , ha v .lowlink = v .index akkor hozzon létre egy új, erősen kapcsolódó komponenst ismétlés w  := verem .pop() w .onStack := false adjuk hozzá w -t az aktuálisan erősen kapcsolódó komponenshez , miközben w ≠ v az erősen csatlakoztatott komponenst adja ki

Nyitva tartás

Az algoritmus időbonyolultságú , ahol  az ívek száma és  a gráf csúcsai [1] .

Lásd még

A Strongly Connected Two-stack Component Search Algorithm  egy hasonló algoritmus, amely mélységi keresést használ.

Jegyzetek

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

Linkek

Irodalom