Algoritmus szorosan összefüggő komponensek keresésére két köteggel

Egy út alapú algoritmus az erősen kapcsolódó irányított gráfkomponensek megtalálására egy olyan algoritmus, amely mélységi keresést használ két veremmel kombinálva, amelyek közül az egyik az aktuális komponens csúcsait, a másik pedig az aktuális útvonalat tárolja [1] . Ennek az algoritmusnak a változatait Purd [2] , Munro [3] , Dijkstra [4] , Cheriyan, Melhorn [5] és Gabov [6] javasolta . Ezek közül a Dijkstra verziója volt az első, amely lineáris időben futott [7]

Leírás

Az algoritmus mélységi keresést hajt végre egy adott G gráfon , fenntartva két verem, az S és a P (a rekurzív függvények normál hívási veremén kívül). Az S verem tartalmazza az összes olyan csúcsot, amely még nincs hozzárendelve egy erősen kapcsolódó komponenshez, abban a sorrendben, ahogyan a mélységi keresés eléri a csúcsot. A P verem olyan csúcsokat tartalmaz, amelyeknél még nincs meghatározva, hogy melyik összefüggő komponenshez tartozik a csúcs. Az algoritmus a C elért csúcsszámlálót is használja, amely a csúcsok előrendelésének kiszámítására szolgál.

Amikor a mélységi keresés eléri a v csúcsot , az algoritmus a következő lépéseket hajtja végre:

  1. A v előrendelési száma C -re van állítva , majd a C növekszik.
  2. A v csúcs S -be és P -be kerül .
  3. Minden v -ből egy szomszédos w csúcsra ívelt ívre :
    • Ha a w előrendelési száma még nincs hozzárendelve, akkor rekurzívan vizsgálja meg w ;
    • Ellenkező esetben, ha w még nincs hozzárendelve egy erősen kapcsolódó komponenshez:
      • Sorozatosan emelje ki a csúcsokat P -ből, amíg a P verem tetején lévő elem előrendelési száma kisebb vagy egyenlő w előrendelési számmal .
  4. Ha v a P verem tetején van :
    • Tolja ki a csúcsokat S -ből, amíg a v csúcs ki nem ugrik, és rendelje hozzá a kitolt csúcsokat az új komponenshez.
    • Nyomja ki a v -t a P -ből .

Az algoritmus abból áll, hogy a gráf csúcsai között hurkolt, rekurzív keresést indítva minden olyan csúcson, amelyhez nincs előrendelési szám.

Kapcsolódó algoritmusok

A leírt algoritmushoz hasonlóan Tarjan algoritmusa az erősen kapcsolódó komponensek megtalálására is mélységi keresést használ egy verem mellett olyan csúcsok tárolására, amelyek még nincsenek hozzárendelve egyetlen erősen kapcsolódó komponenshez sem, és az algoritmus ezeket a csúcsokat egy új komponensbe helyezi át, amikor az algoritmus befejezi a komponens utolsó csúcsának kiterjesztését. Azonban a P verem helyett Tarjan algoritmusa egy csúcsindexelt előrendelési számokból álló tömböt használ, amely abban a sorrendben van hozzárendelve, ahogyan a csúcsok meglátogatták a mélységi keresés során . Az előrendelési tömb arra szolgál, hogy nyomon kövesse, mikor kell új komponenst létrehozni.

Jegyzetek

  1. ↑ Sedgewick, 2004 .
  2. ↑ Purdom, 1970 .
  3. ↑ Munro, 1971 .
  4. ↑ Dijkstra, 1976 .
  5. ↑ Cheriyan, Mehlhorn, 1996 .
  6. ↑ Gabow, 2000 .
  7. ↑ A Path-based DFS for Strong Components története Archiválva : 2017. május 20., a Wayback Machine , Harold N. Gabow, elérve: 2012.04.24.

Irodalom