Algorytm silnych komponentów oparty na ścieżce

W teorii grafów silnie połączone składowe grafu skierowanego można znaleźć za pomocą algorytmu, który wykorzystuje przeszukiwanie w głąb w połączeniu z dwoma stosami , jednym do śledzenia wierzchołków w bieżącym komponencie, a drugim do śledzenia bieżącego ścieżka wyszukiwania. Wersje tego algorytmu zostały zaproponowane przez Purdom (1970) , Munro (1971) , Dijkstra (1976) , Cheriyan i Mehlhorn (1996) oraz Gabow (2000) ; spośród nich wersja Dijkstry była pierwszą, która osiągnęła czas liniowy .

Opis

Algorytm przeprowadza przeszukiwanie w głąb danego grafu G , zachowując tak samo jak dwa stosy S i P (oprócz normalnego stosu wywołań funkcji rekurencyjnej). Stos S zawiera wszystkie wierzchołki, które nie zostały jeszcze przypisane do silnie połączonego komponentu, w kolejności, w jakiej przeszukiwanie w głąb dociera do wierzchołków. Stos P zawiera wierzchołki, które nie zostały jeszcze określone jako należące do różnych silnie połączonych komponentów. Używa również licznika C liczby wierzchołków osiągniętych do tej pory, której używa do obliczenia numerów preorder wierzchołków.

Gdy przeszukiwanie w głąb osiągnie wierzchołek v , algorytm wykonuje następujące kroki:

1. Ustaw numer zamówienia w przedsprzedaży v na C i zwiększ C .
2. Wciśnij v na S , a także na P.
3. Dla każdej krawędzi od v do sąsiedniego wierzchołka w :
   • Jeśli numer w przedsprzedaży nie został jeszcze przypisany (krawędź jest krawędzią drzewa ), przeszukaj rekurencyjnie w ;
   • W przeciwnym razie, jeśli w nie zostało jeszcze przypisane do silnie połączonego komponentu (krawędź jest krawędzią przednią/tylną/skrzyżującą):
     • Wielokrotnie przesuwaj wierzchołki od P , aż górny element P będzie miał numer w przedsprzedaży mniejszy lub równy numerowi w przedsprzedaży z w .
4. Jeśli v jest górnym elementem P :
   • Pop wierzchołki od S do v zostały zdjęte, i przypisz zdjęte wierzchołki do nowego komponentu.
   • Pop V od P. _

Ogólny algorytm składa się z pętli przechodzącej przez wierzchołki grafu, wywołującej to rekurencyjne wyszukiwanie w każdym wierzchołku, który nie ma jeszcze przypisanego numeru zamówienia wstępnego.

Powiązane algorytmy

Podobnie jak ten algorytm, algorytm silnie połączonych komponentów Tarjana również wykorzystuje przeszukiwanie najpierw w głąb wraz ze stosem, aby śledzić wierzchołki, które nie zostały jeszcze przypisane do komponentu, i przenosi te wierzchołki do nowego komponentu, gdy zakończy rozwijanie ostatniego wierzchołka swojego komponentu. część. Jednak zamiast stosu P , algorytm Tarjana wykorzystuje indeksowaną przez wierzchołki tablicę numerów preorderów, przypisywanych w kolejności, w jakiej wierzchołki są odwiedzane po raz pierwszy w przeszukiwaniu w głąb . Tablica preorder służy do śledzenia, kiedy utworzyć nowy komponent.

Notatki

•   Cheriyan, J.; Mehlhorn, K. (1996), „Algorytmy dla gęstych grafów i sieci na komputerze o swobodnym dostępie”, Algorithmica , 15 (6): 521–549, doi : 10.1007 / BF01940880 , S2CID 8930091 .
• Dijkstra, Edsger (1976), Dyscyplina programowania , NJ: Prentice Hall, Ch. 25 .
•   Gabow , Harold N. ( 2000 ) _ _ _ _ _ 00)00051-X , MR 1761551 .
• Munro, Ian (1971), „Wydajne określanie przechodniego zamknięcia skierowanego wykresu”, Information Processing Letters , 1 (2): 56–58, doi : 10.1016/0020-0190 (71) 90006-8 .
•   Purdom, P., Jr. (1970), „Algorytm zamknięcia przechodniego” , BIT , 10 : 76–94, doi : 10,1007/bf01940892 , S2CID 20818200 .
• Sedgewick, R. (2004), „19,8 Silne komponenty w digrafach”, Algorytmy w Javie, część 5 - Algorytmy grafów (wyd. 3), Cambridge MA: Addison-Wesley, s. 205–216 .