Un algoritm pentru găsirea de componente puternic conectate cu două stive

Un algoritm bazat pe cale pentru găsirea componentelor grafului direcționat puternic conectate este un algoritm care utilizează căutarea în adâncime în combinație cu două stive , unul stochând vârfurile componentei curente, iar celălalt stochând calea curentă [1] . Versiuni ale acestui algoritm au fost propuse de Purd [2] , Munro [3] , Dijkstra [4] , Cheriyan, Melhorn [5] și Gabov [6] . Dintre acestea, versiunea lui Dijkstra a fost prima care a rulat în timp liniar [7]

Descriere

Algoritmul efectuează o căutare în profunzime pe un grafic G dat , menținând două stive, S și P (în plus față de stiva de apeluri normală pentru funcțiile recursive). Stiva S conține toate nodurile care nu au fost încă alocate unei componente puternic conectate în ordinea în care căutarea în adâncime ajunge la vârf. Stiva P conține vârfuri pentru care nu este încă determinată care componentă conexă îi aparține vârful. Algoritmul folosește și contorul de vârf atins C , care este folosit pentru a calcula preordinea de vârf.

Când căutarea pe adâncimea întâi atinge vârful v , algoritmul efectuează următorii pași:

  1. Numărul de precomandă al lui v este setat la C și apoi C este incrementat.
  2. Vârful v este plasat în S și în P .
  3. Pentru fiecare arc de la v la un vârf învecinat w :
    • Dacă numărul de precomandă al lui w nu a fost încă atribuit, scanați recursiv w ;
    • În caz contrar, dacă w nu este încă atribuit unei componente puternic conectate:
      • Poziționați secvențial vârfurile din P până când elementul din partea de sus a stivei P are un număr de precomandă mai mic sau egal cu numărul de precomandă al lui w .
  4. Dacă v este în vârful stivei P :
    • Împingeți nodurile din S până când vârful v este ieșit și atribuiți nodurile împinse noii componente.
    • Împingeți v din P .

Algoritmul constă în bucla peste vârfurile graficului, invocând o căutare recursivă pe fiecare vârf căruia nu i se atribuie un număr de precomandă.

Algoritmi înrudiți

Similar cu algoritmul descris, algoritmul lui Tarjan pentru găsirea componentelor puternic conectate folosește, de asemenea, căutarea depth-first împreună cu o stivă pentru a stoca vârfuri care nu sunt încă alocate nici unei componente puternic conectate, iar algoritmul transferă aceste vârfuri la o nouă componentă atunci când algoritmul termină extinderea ultimului vârf al componentei. Cu toate acestea, în loc de o stivă P , algoritmul lui Tarjan folosește o matrice indexată pe vârfuri de numere de preordonare atribuite în ordinea în care sunt vizitate vârfurile în căutarea depth-first . Matricea de precomandă este folosită pentru a ține evidența când trebuie formată o nouă componentă.

Note

  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 Arhivat 20 mai 2017 la Wayback Machine , Harold N. Gabow, accesat 2012-04-24.

Literatură