Algoritmus pro hledání pevně propojených součástí se dvěma sadami

Algoritmus založený na cestě pro nalezení silně propojených složek směrovaného grafu je algoritmus, který používá hledání do hloubky v kombinaci se dvěma zásobníky , z nichž jeden ukládá vrcholy aktuální složky a druhý aktuální cestu [1] . Verze tohoto algoritmu navrhli Purd [2] , Munro [3] , Dijkstra [4] , Cheriyan, Melhorn [5] a Gabov [6] . Z nich byla Dijkstrova verze první, která běžela v lineárním čase [7]

Popis

Algoritmus provádí hloubkové prohledávání daného grafu G , přičemž udržuje dva zásobníky, S a P (kromě normálního zásobníku volání pro rekurzivní funkce). Zásobník S obsahuje všechny vrcholy, které ještě nebyly přiřazeny k silně propojené komponentě v pořadí, ve kterém hloubkové hledání dosáhne vrcholu. Zásobník P obsahuje vrcholy, u kterých ještě není určeno, ke které připojené komponentě vrchol patří. Algoritmus také používá čítač dosažených vrcholů C , který se používá k výpočtu předběžného pořadí vrcholů.

Když prohledávání do hloubky dosáhne vrcholu v , algoritmus provede následující kroky:

  1. Číslo předobjednávky v je nastaveno na C a poté se C zvýší.
  2. Vrchol v je umístěn v S a v P .
  3. Pro každý oblouk z v do sousedního vrcholu w :
    • Pokud předobjednávkové číslo w ještě nebylo přiděleno, rekurzivně naskenujte w ;
    • Jinak, pokud w ještě není přiřazeno k silně připojené komponentě:
      • Postupně vyskládejte vrcholy z P , dokud prvek v horní části zásobníku P nebude mít číslo předobjednávky menší nebo rovné číslu předobjednávky w .
  4. Pokud je v na vrcholu zásobníku P :
    • Posuňte vrcholy z S , dokud se vrchol v nevysune, a přiřaďte posunuté vrcholy nové komponentě.
    • Vytlačte v z P. _

Algoritmus sestává ze smyčkování přes vrcholy grafu, vyvolání rekurzivního vyhledávání na každém vrcholu, který nemá přiřazeno číslo předobjednávky.

Související algoritmy

Podobně jako u popsaného algoritmu, Tarjanův algoritmus pro nalezení silně propojených komponent také používá hloubkové vyhledávání spolu se zásobníkem k uložení vrcholů, které ještě nejsou přiřazeny žádné silně propojené komponentě, a algoritmus přenese tyto vrcholy do nové komponenty, když algoritmus dokončí rozbalení posledního vrcholu komponenty. Namísto zásobníku P však Tarjanův algoritmus používá vertexově indexované pole předobjednávkových čísel přiřazených v pořadí, v jakém jsou vertexy navštěvovány při hledání první hloubky . Pole předobjednávky se používá ke sledování, kdy by měla být vytvořena nová komponenta.

Poznámky

  1. ↑ Sedgewick, 2004 .
  2. ↑ Purdom, 1970 .
  3. ↑ Munro, 1971 .
  4. ↑ Dijkstra, 1976 .
  5. ↑ Cheriyan, Mehlhorn, 1996 .
  6. ↑ Gabow, 2000 .
  7. ↑ Historie DFS založeného na cestě pro silné komponenty Archivováno 20. května 2017 na Wayback Machine , Harold N. Gabow, přístup 2012-04-24.

Literatura