Algoritmi vahvasti toisiinsa liittyvien komponenttien löytämiseen kahdella pinolla

Polkupohjainen algoritmi vahvasti toisiinsa liittyvien suunnattujen graafikomponenttien etsimiseen on algoritmi, joka käyttää syvyyshakua yhdessä kahden pinon kanssa , joista toinen tallentaa nykyisen komponentin kärjet ja toinen nykyisen polun [1] . Tämän algoritmin versioita ovat ehdottaneet Purd [2] , Munro [3] , Dijkstra [4] , Cheriyan, Melhorn [5] ja Gabov [6] . Näistä Dijkstran versio oli ensimmäinen, joka juoksi lineaarisessa ajassa [7]

Kuvaus

Algoritmi suorittaa syvyysensimmäisen haun tietylle graafille G ylläpitäen kahta pinoa, S ja P (normaalin rekursiivisten funktioiden kutsupinon lisäksi). Pino S sisältää kaikki kärjet, joita ei ole vielä osoitettu vahvasti kytketylle komponentille siinä järjestyksessä, jossa syvyysensimmäinen haku saavuttaa kärjen. Pino P sisältää pisteitä, joille ei ole vielä määritetty, mihin yhdistettyyn komponenttiin kärki kuuluu. Algoritmi käyttää myös saavutettua kärkipisteen laskuria C , jota käytetään huippupisteiden ennakkojärjestyksen laskemiseen.

Kun syvyysensimmäinen haku saavuttaa kärjen v , algoritmi suorittaa seuraavat vaiheet:

  1. V :n ennakkotilausnumeroksi asetetaan C ja sitten C :tä kasvatetaan.
  2. Piste v sijoitetaan S :ään ja P :hen .
  3. Jokaiselle kaarelle v :stä viereiseen kärkeen w :
    • Jos w :n ennakkotilausnumeroa ei ole vielä määritetty, skannaa rekursiivisesti w ;
    • Muussa tapauksessa, jos w ei ole vielä määritetty vahvasti yhdistetylle komponentille:
      • Nosta kärjet peräkkäin P :stä, kunnes pinon P yläosassa olevan elementin ennakkotilausnumero on pienempi tai yhtä suuri kuin w :n ennakkotilausnumero .
  4. Jos v on pinon P yläosassa :
    • Työnnä kärkipisteitä ulos S :stä, kunnes kärki v ponnahtaa ulos, ja määritä työnnetyt pisteet uudelle komponentille.
    • Työnnä v ulos P :stä .

Algoritmi koostuu silmukasta graafin kärkien yli ja käynnistää rekursiivisen haun jokaisessa kärjessä, jolle ei ole annettu ennakkotilausnumeroa.

Aiheeseen liittyvät algoritmit

Kuten kuvattu algoritmi, Tarjanin algoritmi vahvasti toisiinsa liittyvien komponenttien löytämiseen käyttää myös syvyyshakua yhdessä pinon kanssa sellaisten pisteiden tallentamiseen, joita ei ole vielä osoitettu millekään vahvasti yhdistetylle komponentille, ja algoritmi siirtää nämä kärjet uuteen komponenttiin, kun algoritmi lopettaa komponentin viimeisen kärjen laajentamisen. Kuitenkin pinon P sijasta Tarjanin algoritmi käyttää vertex-indeksoitua taulukkoa ennakkotilausnumeroista, jotka on määritetty siinä järjestyksessä, jossa kärjet ovat käyty syvyys-ensimmäisessä haussa . Ennakkotilaustaulukon avulla seurataan, milloin uusi komponentti tulisi muodostaa.

Muistiinpanot

  1. ↑ Sedgewick, 2004 .
  2. ↑ Purdom, 1970 .
  3. ↑ Munro, 1971 .
  4. ↑ Dijkstra, 1976 .
  5. ↑ Cheriyan, Mehlhorn, 1996 .
  6. ↑ Gabow, 2000 .
  7. ↑ History of Path-based DFS for Strong Components Arkistoitu 20. toukokuuta 2017, Wayback Machine , Harold N. Gabow, käytetty 24.4.2012.

Kirjallisuus