algorytm.org

Silnie spójne składowe



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Silnie spójne składowe
Ocena użytkowników:***** / 47
SłabyŚwietny 
Wpisany przez Rafał Pytko, 26 września 2009 12:24

Dla grafów nieskierowanych zostało zdefiniowane pojęcie spójnych składowych, czyli maksymalnych fragmentów grafu, które są spójne (pomiędzy każdymi dwoma wierzchołkami istnieje ścieżka). Do sprawdzania czy graf jest spójny oraz znajdowania jego spójnych składowych wykorzystywany jest algorytm DFS lub BFS.

Odpowiednikiem tej definicji dla grafów skierowanych są silnie spójne składowe. Silnie spójna składowa grafu skierowanego, to taki maksymalny podgraf, w którym istnieje ścieżka (skierowana) pomiędzy każdymi dwoma wierzchołkami tego podgrafu. Maksymalny czyli taki, którego nie możemy już powiększyć tak, aby dalej spełniał nasze założenie. Spójrzmy na poniższy przykład.

Przykład:


Uwaga: Na przykład podgraf złożony z wierzchołków (2,3,4) nie jest silnie spójną składową, gdyż nie jest maksymalnym, który spełnia założenie o istnieniu ścieżek. Maksymalny to (2,3,4,7).

silnie spójne składowe


Spójne składowe w naszym przykładzie to:
(1)
(2,3,4,7)
(5,6)

Algorytm:

Aby opisać algorytm wyznaczania silnie spójnych składowych będzie nam potrzebna definicja grafu transponowanego. Graf transponowany jakiegoś grafu powstaje przez zamianę kierunku jego wszystkich krawędzi. Czyli jeśli w naszym oryginalnym grafie występowała krawędź 1 -> 2, to w grafie transponowanym zostanie zamieniona na krawędź 2 -> 1.
Spójrzmy jak wygląda graf transponowany dla grafu z poprzedniego przykładu:

silnie spójne składowe - graf transponowany


Algorytm wyznaczania silnie spójnych składowych grafu skierowanego:
  • Oblicz czasy przetworzenia (post-order) wierzchołków algorytmem przeszukiwania w głąb (DFS).
  • Wywołujemy algorytm DFS dla grafu transponowanego w kolejności malejących czasów przetworzenia wierzchołków. Wszystkie wierzchołki w jednym drzewie przeszukiwania w głąb należą do jednej silnie spójnej składowej.


Przykład:


Spójrzmy na działanie algorytmu dla naszego przykładowego grafu.

Faza 1:
Uruchamiamy algorytm DFS z wierzchołka 1. Idziemy do wierzchołka 2 -> 3 -> 4 -> 5 -> 6 (ustawiając kolejne wierzchołki jako odwiedzone). Z wierzchołka 6 nie możemy już iść do żadnego nieodwiedzonego wierzchołka (5 już był odwiedzony), ustawiamy czas przetworzenia wierzchołka 6 na 1.
Z wierzchołka 5 też nie możemy już nigdzie iść (w 6 już byliśmy) czyli czas przetworzenia ustawiamy na 2.
Z wierzchołka 4 idziemy do 7. Z wierzchołka 7 nie możemy już nigdzie iść (wierzchołek 2 już jest odwiedzony), czyli czas przetworzenia 7-mki to 3.
Teraz już nie możemy nigdzie iść z wierzchołka 4, czyli czas przetworzenia ustawiamy na 4.
Z wierzchołka 3 też już nigdzie nie możemy iść, czas przetworzenia 5.
Tak samo dla wierzchołka 2, czas przetworzenia 6.
Tak samo dla wierzchołka 1, czas przetworzenia 7.

Faza 2:
Będziemy rozpatrywać wierzchołki w kolejności malejących czasów przetworzenia czyli: Wierzchołki nr: 1, 2, 3, 4, 7, 5, 6
W grafie transponowanym startujemy algorytm DFS.
Zaczynamy z wierzchołka 1.
Odwiedzimy tylko wierzchołek nr 1. Jest to nasza pierwsza silnie spójna składowa.
Startujemy z wierzchołka 2.
Odwiedzamy 2, 7, 4, 3. Jest to nasza druga silnie spójna składowa.
Z wierzchołków 3, 4 i 7 nie startujemy, bo już były odwiedzone.
Startujemy z wierzchołka 5.
Odwiedzamy 5 i 6. Jest to kolejna silnie spójna składowa.
Z wierzchołka 6 nie startujemy, bo już był odwiedzony wcześniej.

W ten sposób uzyskaliśmy trzy silnie spójne składowe: (1), (2,3,4,7) oraz (5,6).

Graf silnie spójnych składowych:

Zauważmy, że po obliczeniu silnie spójnych składowych możemy "skompresować" nasz graf. Wierzchołki odpowiadają silnie spójnym składowym. Pomiędzy dwoma silnie spójnymi składowymi jest krawędź, jeśli istniała krawędź pomiędzy dwoma wierzchołkami z tych składowych. Taki graf nie zawiera cykli, gdyż byłoby to sprzeczne z tym, że silnie spójne składowe są maksymalne.

silnie spójne składowe


Zastosowanie:

Złożoność czasowa tego algorytmu jest liniowa względem liczby wierzchołków i krawędzi, jest to dwukrotne wywołanie algorytmu przeszukiwania w głąb. Jest to zatem szybki algorytm.
Czasami zachodzi potrzeba przekształcenia naszego grafu w graf bez cykli i dalszego operowania na takim grafie, wówczas możemy zastosować powyższy algorytm.
Mając daną sieć dróg pomiędzy miastami (drogi jednokierunkowe) chcemy sprawdzić czy z każdego miasta da się dojechać do każdego innego. Wówczas wystarczy sprawdzić czy nasz graf jest jedną silnie spójną składową. Wyznaczanie silnie spójnych składowych grafu jest również wykorzystywane w algorytmie spełnialności formuł dwuargumentowych (2SAT).



Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Rafał PytkoC/C++
.cpp
.cpp
***** / 15
Emil HotkowskiC/C++SSS na vectorach
.cpp
.cpp
***** / 6
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 15 stycznia 2012 20:10
Komentarze
photo
+3 # Anka 2009-12-14 16:11
Bardzo fajny artykuł. Ładnie wytłumaczone, a że na przykładzie to zawsze można sprawdzić czy nasz program też zwraca to samo. Ogółem ślicznie.
Wypadałoby jednak wspomnieć że jest to algorytm Kosaraju. Właściwie to szukając Kosaraju przez polskie Google nic się nie dowiemy, dopiero angielska Wikipedia przybliża sprawę -
To trochę utrudnia poszukiwania. Ale jeśli będziemy go szukać ze względu na zastosowanie to faktycznie łatwo znaleźć
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+2 # Borneq 2011-11-24 16:29
Wierzchołek 1 został potraktowany jako składowa silnie spójna. Ale w tym przypadku nie ma cyklu z tego wierzchołka na niego samego. Czy jeśli będzie, otrzymamy taki sam wynik?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+3 # Borneq 2012-12-24 21:36
A jak jest po angielski "silnie spójna składowa"?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+5 # Fengson 2013-01-06 17:40
SCC–strongly connected component
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz