Silnie spójna składowa jest to maksymalny zbiór wierzchołków (podgraf) pewnego grafu, w którym to zbiorze istnieją połączenia bezpośrednie bądź pośrednie między wszystkimi parami wierzchołków (innymi słowy: można dotrzeć z każdego wierzchołka do każdego innego w danym zbiorze).

W każdym grafie skierowanym możemy dokonać podziału na silnie spójne składowe. Dokonuje się tego za pomocą dwóch przeszukiwań w głąb. Najpierw wykonujemy operację przeszukiwania w głąb dla każdego, nieprzetworzonego wierzchołka, dokonując przy tym zapamiętywania czasów przetworzenia. Następnie odwracamy wszystkie krawędzie grafu (krawędź prowadząca od wierzchołka a do b, powinna prowadzić z b do a). Należy zwrócić uwagę, iż ten graf będzie posiadał te same silnie spójne składowe, co graf przed transformacją. Po odwróceniu dokonujemy kolejnych przeszukiwań w głąb, tym razem rozpoczynając przeszukiwanie od wierzchołków z największym (najpóźniejszym) czasem przetworzenia (kolejność wierzchołków wywoływanych wewnątrz procedury DFS[#]_ nie ma już znaczenia). Wszystkie wierzchołki, które zostały odwiedzone w następstwie wywołania procedury DFS, są elementami zbioru, który to stanowi jedną silnie spójną składową. Operację wywoływania procedury przeszukiwania w głąb powtarzamy dopóty, dopóki pozostają jeszcze nieodwiedzone wierzchołki, pamiętając o zachowaniu kolejności odwiedzania według malejących czasów przetworzenia. W ten sposób dokonamy podziału grafu na silnie spójne składowe, a ilość wywołań procedury DFS przez główną pętlę programu będzie równa ilości silnie spójnych składowych w grafie.

Czas działania algorytmu wynosi O(V + E), gdzie V to ilość wierzchołków oraz E to ilość krawędzi (bierze się to z czasu działania przeszukiwania w głąb).

Zastosowanie

Za pomocą algorytmu podziału grafu na silnie spójne składowe uzyskujemy podział grafu na obszary, wewnątrz których istnieje nieskończenie wiele sposobów dojścia między każdą parą wierzchołków przy założeniu, iż pojedyncza ścieżka może prowadzić przez każdą krawędź nieskończenie wiele razy. Podział na silnie spójne składowe jest przydatny przy niektórych problemach szukania najkrótszych ścieżek oraz innych problemach wymagających zastosowanie grafów, jednakże trudno jednoznacznie zdefiniować przykłady owych problemów.

Implementacja

Przy implementacji algorytmu posłużymy się procedurą DFS oraz tablicą czas_przetworzenia z artykułu pt. Przeszukiwanie w głąb (DFS). Odwracanie krawędzi najlepiej rozwiązać, tworząc nowy graf, dodając do niego odwróconą krawędź. Poniżej implementacja algorytmu zapisana za pomocą pseudokodu:

for każdy wierzchołek grafu do
{
if czas_odwiedzenia[wierzchołek] == 0 then
{
wywołaj procedurę DFS ( wierzchołek )
}
}

for każdy wierzchołek grafu do
{
for każda krawędź wychodząca z tego wierzchołka do
{
dodaj odwróconą krawędź do nowego grafu
}
}

utwórz tablicę_wierzchołków
przypisz każdej komórce tablicy_wierzchołków początkową wartość równą numerowi kolejnego wierzchołka

posortuj tablicę_wierzchołków malejąco ze względu na wartość komórki czas_przetworzenia[wartość aktualnej komórki w tablicy_wierzchołków]

wyzeruj wszystkie wartości tablicy czas_odwiedzenia

for od i = 1 do i=ilość wierzchołków w grafie do
{
if czas_odwiedzenia[ tablica_wierzchołków[i] ] == 0 then
{
wywołaj procedurę DFS ( tablica_wierzchołków[i] )
wypisz wszystkie nowoodwiedzone wierzchołki jako zbiór wierzchołków jednej silnie spójnej składowej
}
}

.. [#] Por. z artykułem: Przeszukiwanie w głąb (DFS)