En algoritm för att hitta starkt anslutna komponenter med två staplar

En vägbaserad algoritm för att hitta starkt anslutna riktade grafkomponenter är en algoritm som använder djup-först-sökning i kombination med två stackar , en lagrar hörn av den aktuella komponenten och den andra lagrar den aktuella vägen [1] . Versioner av denna algoritm har föreslagits av Purd [2] , Munro [3] , Dijkstra [4] , Cheriyan, Melhorn [5] och Gabov [6] . Av dessa var Dijkstras version den första som kördes i linjär tid [7]

Beskrivning

Algoritmen utför en djup-först-sökning på en given graf G och bibehåller två stackar, S och P (utöver den normala anropsstacken för rekursiva funktioner). Stacken S innehåller alla hörn som ännu inte har tilldelats en starkt ansluten komponent i den ordning som djupet-första sökningen når vertexet. Stack P innehåller hörn för vilka det ännu inte är bestämt vilken ansluten komponent vertexen tillhör. Algoritmen använder också räknaren för uppnådda vertex C , som används för att beräkna vertexförordningen.

När sökningen på djupet först når vertex v utför algoritmen följande steg:

  1. Förbeställningsnumret för v sätts till C och sedan ökas C.
  2. Spetsen v placeras i S och i P .
  3. För varje båge från v till en angränsande vertex w :
    • Om förbeställningsnumret för w ännu inte har tilldelats, skanna w rekursivt ;
    • Annars, om w ännu inte är tilldelad till en starkt ansluten komponent:
      • Poppa sekventiellt hörnen från P tills elementet överst i stapeln P har ett förbeställningsnummer som är mindre än eller lika med förbeställningsnumret på w .
  4. Om v är överst i stack P :
    • Tryck ut hörn från S tills vertex v är utfälld, och tilldela de skjutna hörnen till den nya komponenten.
    • Tryck v ur P .

Algoritmen består av att loopa över grafens hörn och anropa en rekursiv sökning på varje vertex som inte är tilldelat ett förbeställningsnummer.

Relaterade algoritmer

I likhet med den beskrivna algoritmen använder Tarjans algoritm för att hitta starkt anslutna komponenter också djup-först-sökning tillsammans med en stack för att lagra hörn som ännu inte är tilldelade någon starkt ansluten komponent, och algoritmen överför dessa hörn till en ny komponent när algoritmen avslutar utvidgningen av komponentens sista hörn. Men istället för en stack P använder Tarjans algoritm en vertexindexerad array av förbeställningsnummer som tilldelas i den ordning som hörnen besöks i djupet-först-sökningen . Förbeställningsmatrisen används för att hålla reda på när en ny komponent ska bildas.

Anteckningar

  1. ↑ Sedgewick, 2004 .
  2. ↑ Purdom, 1970 .
  3. ↑ Munro, 1971 .
  4. ↑ Dijkstra, 1976 .
  5. ↑ Cheriyan, Mehlhorn, 1996 .
  6. ↑ Gabow, 2000 .
  7. ↑ Historik om sökvägsbaserad DFS för starka komponenter Arkiverad 20 maj 2017 på Wayback Machine , Harold N. Gabow, tillgänglig 2012-04-24.

Litteratur