Algorytm silnie połączonych komponentów Tarjana

Algorytm silnie połączonych komponentów Tarjana

Animacja algorytmu Tarjana
Struktura danych	Wykres
Wydajność w najgorszym przypadku	${\ Displaystyle O (| V | + | E |)}$

Algorytm silnie połączonych komponentów Tarjana to algorytm w teorii grafów służący do znajdowania silnie połączonych komponentów (SCC) grafu skierowanego . Działa w czasie liniowym , dopasowując się do ograniczeń czasowych metod alternatywnych, w tym algorytmu Kosaraju i algorytmu silnych komponentów opartych na ścieżkach . Algorytm został nazwany na cześć jego wynalazcy, Roberta Tarjana .

Przegląd

Algorytm pobiera graf skierowany jako dane wejściowe i tworzy podział wierzchołków grafu na silnie powiązane składowe grafu. Każdy wierzchołek grafu występuje dokładnie w jednym z silnie powiązanych składników. Każdy wierzchołek, który nie znajduje się w cyklu skierowanym, sam tworzy silnie powiązany komponent: na przykład wierzchołek, którego stopień wejściowy lub wyjściowy wynosi 0, lub dowolny wierzchołek wykresu acyklicznego.

Podstawowa idea algorytmu jest następująca: przeszukiwanie w głąb (DFS) rozpoczyna się od dowolnego węzła początkowego (a kolejne przeszukiwania w głąb są przeprowadzane na wszystkich węzłach, które nie zostały jeszcze znalezione). Jak zwykle w przypadku przeszukiwania w głąb, wyszukiwanie odwiedza każdy węzeł grafu dokładnie raz, odrzucając ponowne odwiedzanie każdego węzła, który został już odwiedzony. Zatem kolekcja drzew wyszukiwania jest lasem obejmującym wykresu. Silnie połączone komponenty zostaną odzyskane jako pewne poddrzewa tego lasu. Korzenie tych poddrzew nazywane są „korzeniami” silnie połączonych komponentów. Dowolny węzeł silnie połączonego komponentu może służyć jako root, jeśli jest pierwszym węzłem komponentu wykrytym przez wyszukiwanie.

Niezmiennik stosu

Węzły są umieszczane na stosie w kolejności, w jakiej są odwiedzane. Kiedy przeszukiwanie w głąb rekurencyjnie odwiedza węzeł v i jego potomków, te węzły niekoniecznie są usuwane ze stosu, gdy to rekurencyjne wywołanie powraca. Kluczowa niezmienna właściwość polega na tym, że węzeł pozostaje na stosie po odwiedzeniu go wtedy i tylko wtedy, gdy istnieje ścieżka w grafie wejściowym od tego węzła do jakiegoś węzła znajdującego się wcześniej na stosie. Innymi słowy, oznacza to, że w DFS węzeł zostałby usunięty ze stosu dopiero po przejściu wszystkich połączonych z nim ścieżek. Kiedy DFS cofnie się, usunie węzły na pojedynczej ścieżce i powróci do katalogu głównego, aby rozpocząć nową ścieżkę.

Na końcu wywołania, które odwiedza v i jego potomków, wiemy, czy sam v ma ścieżkę do dowolnego węzła znajdującego się wcześniej na stosie. Jeśli tak, wywołanie powraca, pozostawiając v na stosie, aby zachować niezmiennik. Jeśli nie, to v musi być korzeniem jego silnie połączonego komponentu, który składa się z v wraz z węzłami znajdującymi się później na stosie niż v (wszystkie takie węzły mają ścieżki z powrotem do v , ale nie do żadnego wcześniejszego węzła, ponieważ gdyby miały ścieżki do wcześniejszych węzłów niż v miałby również ścieżki do wcześniejszych węzłów, co jest fałszywe). Połączony komponent zakorzeniony w v jest następnie zdejmowany ze stosu i zwracany, ponownie zachowując niezmiennik.

Księgowość

Każdemu węzłowi v jest przypisana unikalna liczba całkowita v.index , która numeruje węzły kolejno w kolejności, w jakiej zostały odkryte. Zachowuje również wartość v.lowlink , która reprezentuje najmniejszy indeks dowolnego węzła na stosie, o którym wiadomo, że jest osiągalny od v do poddrzewa DFS v, w tym samego v . Dlatego v musi zostać pozostawione na stosie, jeśli v.lowlink < v.index , podczas gdy v musi zostać usunięte jako korzeń silnie połączonego komponentu, jeśli v.lowlink == v.index . Wartość v.lowlink jest obliczana podczas przeszukiwania w głąb z v , ponieważ znajduje węzły, które są osiągalne z v .

Zauważ, że lowlink różni się od lowpoint, który jest najmniejszym indeksem osiągalnym od v do dowolnej części wykresu.

Algorytm w pseudokodzie

        
          algorytm  tarjan  jest  wejściem:  graph  G  = (  V  ,  E  )  wyjście:  zbiór silnie połączonych komponentów (zbiorów wierzchołków)  index  := 0  S  := pusty stos  dla każdego  v  w  V  do  jeśli  v  .index jest niezdefiniowany  to  strongconnect(  v  )  funkcja  silne połączenie(  v  ) 
        
        
        
          
             
                 // Ustaw indeks głębokości dla v na najmniejszy nieużywany indeks  v  .index :=  index  v  .lowlink :=  index  index  :=  index  + 1  S  .push(  v  )  v  .onStack := true  // Rozważ następniki v  for each  (  v  ,  w  )  w  E  do  jeśli  w  .index jest niezdefiniowany  to  // Następca w nie został jeszcze odwiedzony; powtarzać się na nim   
                
                
                
                 strongconnect(  w  )  v  .lowlink := min(  v  .lowlink,  w  .lowlink)  else if  w  .onStack  then  // Następca w jest na stosie S, a zatem w bieżącym SCC  // Jeśli  w  nie ma na stosie, to (  v  ,  w  ) to krawędź wskazująca na już znaleziony SCC i musi zostać zignorowana  // Uwaga: Następna linia może wyglądać dziwnie - ale jest poprawna.  // Mówi w.index nie w.lowlink; to jest celowe i pochodzi z oryginalnej pracy  
                
         
                  v  .lowlink := min(  v  .lowlink,  w  .index)  // Jeśli v jest węzłem głównym, zdejmij stos i wygeneruj SCC,  jeśli  v  .lowlink =  v  .index  następnie  rozpocznij nowy silnie połączony komponent  powtórz  w  :=  S  .pop()  w  .onStack := false dodaj  w  do aktualnie silnie połączonego komponentu  podczas gdy  w  ≠  v  Wyprowadź prąd silnie podłączony komponent 

Zmienna indeksu jest licznikiem numerów węzłów przeszukiwania w pierwszej kolejności. S to stos węzłów, który zaczyna się od pustego i przechowuje historię eksplorowanych węzłów, ale jeszcze nie przypisanych do silnie połączonego komponentu. Zauważ, że nie jest to normalny stos wyszukiwania w głąb, ponieważ węzły nie są usuwane, gdy wyszukiwanie powraca w górę drzewa; są one otwierane tylko wtedy, gdy zostanie znaleziony cały silnie połączony komponent.

Najbardziej zewnętrzna pętla przeszukuje każdy węzeł, który nie został jeszcze odwiedzony, zapewniając, że węzły, które nie są osiągalne z pierwszego węzła, zostaną ostatecznie pokonane. Funkcja strongconnect wykonuje pojedyncze przeszukiwanie grafu w głąb, znajdując wszystkie następniki z węzła v i zgłaszając wszystkie silnie połączone składowe tego podgrafu.

Kiedy każdy węzeł kończy rekursję, jeśli jego lowlink jest nadal ustawiony na swój indeks, to jest to węzeł główny silnie połączonego komponentu, utworzonego przez wszystkie węzły nad nim na stosie. Algorytm podnosi stos do bieżącego węzła włącznie i przedstawia wszystkie te węzły jako silnie połączony komponent.

Zauważ, że v .lowlink := min( v .lowlink, w .index) to właściwy sposób aktualizacji v.lowlink , jeśli w jest na stosie. Ponieważ w jest już na stosie, (v, w) jest tylną krawędzią w drzewie DFS, a zatem w nie znajduje się w poddrzewie v . Ponieważ v.lowlink bierze pod uwagę węzły dostępne tylko przez węzły w poddrzewie v , musimy zatrzymać się na w i użyć w.index zamiast w. lowlink .

Złożoność

Złożoność czasowa : Procedura Tarjana jest wywoływana raz dla każdego węzła; instrukcja forall uwzględnia każdą krawędź co najwyżej raz. Czas działania algorytmu jest zatem liniowy pod względem liczby krawędzi i węzłów w G, tj. ${\ Displaystyle O (| V | + | E |)}$ .

Aby osiągnąć tę złożoność, test na to, czy w jest na stosie, powinien być wykonywany w stałym czasie. Można to zrobić, na przykład, przechowując flagę w każdym węźle, która wskazuje, czy znajduje się on na stosie, i wykonując ten test, sprawdzając flagę.

Złożoność przestrzenna : Procedura Tarjana wymaga dwóch słów danych uzupełniających na wierzchołek dla pól index i lowlink , wraz z jednym bitem dla onStack i innym dla określenia, kiedy indeks jest niezdefiniowany. Ponadto jedno słowo jest wymagane w każdej ramce stosu do przechowywania v , a drugie do bieżącej pozycji na liście krawędzi. Wreszcie rozmiar stosu S w najgorszym przypadku musi wynosić ${\ Displaystyle | V|}$ (tj. gdy wykres jest jednym gigantycznym elementem). $_$ ostateczną _ $_$ _ Odmiana Nuutila i Soisalon-Soininen zredukowała to do ${\ Displaystyle O (| V | \ cdot (1 + 4 w))}$ a następnie Pearce'a wymaga tylko ${\ Displaystyle O (| V | \ cdot (1 + 3w))}$ .

Dodatkowe uwagi

Chociaż nie ma nic specjalnego w kolejności węzłów w każdym silnie połączonym komponencie, jedną użyteczną właściwością algorytmu jest to, że żaden silnie połączony komponent nie zostanie zidentyfikowany przed którymkolwiek z jego następców. Dlatego kolejność, w jakiej identyfikowane są silnie połączone komponenty, stanowi odwrotny rodzaj topologiczny DAG utworzonego przez silnie połączone komponenty.

Donald Knuth opisał algorytm SCC Tarjana jako jedną z jego ulubionych implementacji w książce The Stanford GraphBase .

Napisał także:

Struktury danych, które opracował dla tego problemu, pasują do siebie w zdumiewająco piękny sposób, dzięki czemu wielkości, na które trzeba patrzeć podczas badania skierowanego wykresu, są zawsze magicznie na wyciągnięcie ręki. Jego algorytm wykonuje również sortowanie topologiczne jako produkt uboczny.

Linki zewnętrzne

• Rosetta Code , pokazujący implementacje w różnych językach
• Implementacja PHP silnie połączonego algorytmu komponentów Tarjana
• Implementacja JavaScript algorytmu silnie połączonych komponentów Tarjana