Z poprzedniego wykładu wiemy, że gdy celem jest ułożenie algorytmu o złożoności liniowej ze względu na rozmiar grafu (czyli sumę liczb wierzchołków i krawędzi), graf powinien być reprezentowany przez listy sąsiedztw. Na tym wykładzie przyjmiemy taką właśnie reprezentację grafu wejściowego. Rozwiązanie każdego problemu grafowego, które zależy od poznania struktury połączeń w całym grafie, wymaga przeszukania jego wierzchołków i krawędzi. Takie przeszukanie polega na odwiedzeniu każdego wierzchołka i zbadaniu krawędzi opuszczających już odwiedzone wierzchołki. Jeśli okazuje się, że drugi koniec badanej krawędzi nie był jeszcze odwiedzony, dołącza się go do zbioru wierzchołków odwiedzonych. Przeszukiwania dokonujemy z wykorzystaniem dynamicznego zbioru \( S \), w którym przechowujemy odwiedzane wierzchołki i których sąsiedztwa nie są jeszcze do końca zbadane. Zakładamy, że na zbiorze \( S \) wykonywane są następujące operacje:
\( Insert(S,v) \): wstaw do zbioru \( S \) wierzchołek \( v \);
\( Get(S) \): funkcja, której wynikiem jest (dowolny) wierzchołek z \( S \), wywoływana tylko wtedy, gdy \( S \ne \emptyset \);
\( Delete(S,v) \): usuń z \( S \) wierzchołek \( v \) (zazwyczaj będzie to wierzchołek \( Get(S) \).
Informacje o tym, które wierzchołki zostały już odwiedzone, będziemy przechowywać w tablicy logicznej \( visited[1..n] \). Wartością \( visited[v] \) jest PRAWDA (TRUE) wtedy i tylko wtedy, gdy wierzchołek \( v \) został już odwiedzony. Do przechodzenia list sąsiedztw posłuży nam tablica \( current[1..n] \). Wartością \( current[v] \) jest pierwszy wierzchołek na liście \( L[v] \) - sąsiad \( v \) - który nie był jeszcze oglądany od strony \( v \), co oznacza że krawędź opuszczająca \( v \) w kierunku tego sąsiada nie została jeszcze zbadana.
Inicjacja każdego przeszukiwania wygląda następująco:
for each v \in V do begin current[v] := pierwszy wierzchołek na liście sąsiedztwa L[v]; visited[v] := FALSE; //markujemy, że wierzchołek v nie był jeszcze odwiedzony end;
Załóżmy, że przeszukiwanie grafu rozpoczynamy z wybranego wierzchołka \( s \). Wówczas schemat przeszukiwania z \( s \) można zapisać następująco.
Algorytm Przeszukiwanie grafu - algorytm generyczny
procedure Search(s); begin S := {s}; visited[s] := TRUE; //markujemy s jako odwiedzony while S <> \emptyset do begin u := Get(S); if current[u] <> NIL then //jeśli nie wyczerpaliśmy całej listy sąsiadów wierzchołka u begin //pobierz kolejny wierzchołek z listy sąsiadów i przejdź do następnego // wierzchołka na liście v:= current[u]; current[u] := next(current[u]); if NOT visisted[v] then //jeśli v nie był jeszcze odwiedzony begin visited[v] := TRUE;// markujemy v jako odwiedzony Insert(S,v) //wstaw v do zbioru S end end else //wszystkie krawędzie opuszczające u zostały już zbadane Delete(S,u) end end
Powyższy schemat może być użyty do rozwiązania jednego z najbardziej podstawowych problemów grafowych - problemu spójności. Problem ten formułuje się następująco.
Dane
Graf G=(V,E) (zadany przez listy sąsiedztw)
Wynik
Tablica \( c[1..n] \) o wartościach w zbiorze wierzchołków \( V \) taka, że \( c[u]=c[v] \) wtedy i tylko wtedy, gdy \( u \) i \( v \) należą do tej samej spójnej składowej.
Zauważmy, że problem spójności bardzo łatwo rozwiązać przy użyciu procedury \( Search(s) \). Jeśli przeszukiwanie rozpoczynamy od nieodwiedzonego wierzchołka \( s \), to w wyniku wykonania \( Search \) zostaną odwiedzone wszystkie wierzchołki w grafie \( G \) osiągalne z \( s \). Innymi słowy odwiedzona zostanie cała spójna składowa zawierająca \( s \). Jeśli dla każdego nowo odwiedzanego wierzchołka \( v \) wykonamy przypisanie \( c[v] := s \), po zakończeniu przeszukiwania spójnej składowej zawierającej \( s \), wartość \( c \) każdego wierzchołka w tej składowej będzie właśnie równa \( s \). Jedyne miejsce, w którym musimy zmieniać procedurę \( Search \) jest wiersz 16. Nowy wiersz 16 powinien mieć postać:
16 visited[v]:=TRUE; c[v]:= s;
Tak zmodyfikowaną procedurę \( Search \) nazwiemy \( SearchCC \) z angielskiego Search Connected Components (czyli wyszukaj spójne składowe). Oto algorytm obliczania spójnych składowych z wykorzystaniem procedury \( SearchCC \).
Inicjacja przeszukiwania grafu. for each v \in V do if NOT visited[v] then //odkryta została nowa spójna składowa zawierająca wierzchołek v SearchCC(v);
Dokonamy teraz analizy złożoności algorytmu obliczania spójnych składowych. Zakładamy przy tym, że każda z operacji na pomocniczym zbiorze \( S \) jest wykonywana w czasie stałym. Zauważmy, że każdy wierzchołek jest dokładnie raz wstawiany do zbioru \( S \) - w momencie odkrycia go jako nieodwiedzonego - i dokładnie raz jest usuwany ze zbioru \( S \) - po zbadaniu całego jego sąsiedztwa. Sąsiadów wierzchołka przeglądamy przechodząc po jego liście sąsiedztwa, a dla każdego elementu listy obliczenia z nim związane zajmują stały czas. Jeśli wierzchołek był już odwiedzony, nic nie robimy, natomiast jeśli nie był odwiedzony, markujemy go jako odwiedzonego i wstawiamy do zbioru \( S \). Obliczenia związane z przeglądaniem sąsiedztw wierzchołków zajmują więc czas proporcjonalny do sumy długości list sąsiedztw, która to suma wynosi \( 2m \). Z naszej analizy wynika, że problem spójnych składowych można rozwiązać w czasie \( O(n+m) \), czyli liniowym ze względu na rozmiar grafu.
W dalszym ciągu tego wykładu będziemy rozważali tylko grafy spójne. Niech \( G=(V,E) \) będzie grafem spójnym, a \( s \) wyróżnionym wierzchołkiem w \( G \). Zanalizujmy raz jeszcze wykonanie procedury \( Search(s) \) dla grafu \( G \). Dla każdego wierzchołka \( v \ne s \) niech \( p[v] \) będzie wierzchołkiem z którego wierzchołek \( v \) zostaje odwiedzony, tzn. \( p[v] \) zostaje zamarkowany jako odwiedzony w wierszu 16, gdy zostaje odkryty na liście sąsiedztwa \( v \). Nietrudno zauważyć, że graf \( (V,\{v-p[v]: v \in V-\{s\}\}) \) jest drzewem rozpinającym grafu \( G \). Jeśli każdą krawędź tego drzewa zorientujemy od \( p[v] \) do \( v \), otrzymamy drzewo o korzeniu \( s \), w którym krawędzie są skierowane od korzenia w kierunku liści. Takie drzewo będziemy nazywali drzewem przeszukiwania grafu. Zauważmy, że wskaźniki \( p \) wyznaczają dla każdego wierzchołka \( v \) jedyną ścieżkę w drzewie łączącą \( v \) z korzeniem \( s \).
Dotychczas nic nie mówiliśmy o implementacji zbioru \( S \). Rozważymy dwie naturalne implementacje. W pierwszej z nich zbiór \( S \) jest kolejką typu FIFO. W tej implementacji wynikiem funkcji \( Get(S) \) jest ten wierzchołek ze zbioru \( S \), który przebywa w nim najdłużej. W drugiej implementacji zbiór \( S \) jest stosem, a wynikiem \( Get(S) \) jest wierzchołek przebywający w \( S \) najkrócej, czyli ostatnio wstawiony. Kolejkę i stos łatwo zaimplementować w taki sposób, żeby każda z wymaganych przez nas operacji na zbiorze \( S \) była wykonywana w czasie stałym. W tym celu można użyć struktury listowej.
Czym jest drzewo przeszukiwania, gdy do implementacji zbioru \( S \) użyjemy kolejki? Zauważmy, że do zbioru \( S \) wierzchołki są wstawiane w następującej kolejności. Najpierw pojawia się w \( S \) wyróżniony wierzchołek \( s \). Wierzchołek \( s \) zostanie usunięty (z początku) kolejki dopiero po przejrzeniu jego całej listy sąsiedztwa i wrzuceniu każdego napotkanego na niej wierzchołka na koniec kolejki. Następnie dla każdego sąsiada \( s \) przeglądana jest jego lista sąsiedztwa i każdy wierzchołek dotychczas jeszcze nieodwiedzony zostaje zamarkowany jako odwiedzony i umieszczony na końcu kolejki. W ten sposób po sąsiadach wierzchołka \( s \) w kolejce pojawią się wszyscy sąsiedzi sąsiadów \( s \), którzy nie sąsiadują bezpośrednio z \( s \). W dalszej kolejności w zbiorze \( S \) pojawią się sąsiedzi sąsiadów sąsiadów \( s \), sąsiedzi sąsiadów sąsiadów sąsiadów \( s \), itd. Podzielmy zbiór wierzchołków grafu na warstwy \( W_0, W_1, W_2, \ldots \). Warstwa \( W_0 \) składa się tylko z wierzchołka \( s \). Warstwa \( W_1 \) to sąsiedzi \( s \). Warstwa \( W_2 \) to te wierzchołki grafu, które sąsiadują z co najmniej jednym wierzchołkiem z warstwy \( W_1 \) i nie należą do żadnej z warstw poprzednich, czyli \( W_0 \) i \( W_1 \). Do warstwy \( W_3 \) należą wierzchołki sąsiadujące z co najmniej jednym wierzchołkiem z warstwy poprzedniej (\( W_2 \)) i nie należą do warstw o numerach mniejszych od 3, itd. Nietrudno zauważyć, że \( i \)-ta warstwa składa się ze wszystkich tych wierzchołków, których odległość (długość najkrótszej ścieżki) od \( s \) w grafie \( G \) wynosi dokładnie \( i \). Dla każdego wierzchołka \( v \) wskaźniki \( p[v], p[p[v]],\ldots \) wyznaczają najkrótszą ścieżkę łączącą \( v \) z \( s \). Kolejność w jakiej przeszukiwane są wierzchołki grafu w tym przypadku usprawiedliwia nazwę tego sposobu przeszukiwania jako przeszukiwania wszerz (ang. Breadth First Search, w skrócie BFS). Przemieszczamy się po grafie całą jego szerokością, warstwa po warstwie. Z naszych rozważań wynika, że drzewo przeszukiwania wszerz jest drzewem najkrótszych ścieżek łączących wierzchołki grafu z wyróżnionym wierzchołkiem \( s \). Wynika stąd, że najkrótsze ścieżki łączące wszystkie wierzchołki grafu z jednym wyróżnionym wierzchołkiem można wyznaczyć w czasie liniowym, o ile tylko długości (wagi) krawędzi są jednostkowe.
Z przeszukiwaniem w głąb (ang. Depth First Search, w skrócie DFS) mamy do czynienia, gdy do implementacji zbioru \( S \) używamy stosu. Określenie "przeszukiwanie w głąb" bierze się stąd, że zawsze próbujemy kontynuować przeszukiwanie z najpóźniej odkrytego wierzchołka, czyli z tego, który znajduje się na szczycie stosu. Okazuje się, że przeszukując graf w głąb możemy zebrać niezmiernie przydatne informacje o strukturze grafu, które mogą być wykorzystane w konstruowaniu efektywnych algorytmów dla bardzo wielu problemów grafowych. Przeszukiwanie w głąb dużo wygodniej opisać rekurencyjnie. Rozważmy poniższą procedurę \( DFS(v) \), w której dodatkowo numerujemy wierzchołki w kolejności odwiedzania. W tym celu użyjemy globalnej zmiennej \( ost{nr} \), której wartością jest ostatnio nadany numer. Zmienną \( ost{nr} \) inicjujemy na 0. Otrzymaną numerację będziemy nazywali numeracją w głąb.
Algorytm Przeszukiwanie w głąb
procedure DFS(v); //v jest nowo odkrytym wierzchołkiem begin //markujemy v jako odwiedzony visited[v] :=TRUE; //wierzchołkowi v nadajemy kolejny numer ostnr := ostnr + 1; nr[v] := ostnr; //przeglądamy listę sąsiedztwa v i dla każdego nowo odkrytego //wierzchołka wywołujemy procedurę DFS for each u \in L[v] do if NOT visited[u] then DFS(u) end;
Jeśli chcemy przeszukać graf poczynając od wierzchołka \( s \), wystarczy wywołać \( DFS(s) \), inicjując wcześniej tablice \( visited \) i \( current \) oraz zmienną \( ost{nr} \). Zauważmy, że krawędź \( v--u \) zaliczamy do drzewa przeszukiwania (w głąb), jeśli po wejściu do wierzchołka \( v \) odkrywamy, że wierzchołek \( u \) na liście sąsiedztwa \( v \) nie został jeszcze odwiedzony. Krawędzie, które nie należą do drzewa przeszukiwania mają jedną bardzo ważną własność.
Krawędź niedrzewowa łączy zawsze potomka z przodkiem w drzewie przeszukiwania w głąb.
Dowód powyższej własności jest niezwykle prosty. Załóżmy nie wprost, że istnieje niedrzewowa krawędź \( v-u \) taka, że wierzchołki \( v \), \( u \) nie są w relacji potomek-przodek. Bez straty ogólności możemy przyjąć, że \( v \) zostaje odwiedzony wcześniej niż \( u \). Załóżmy, że \( u \) zostaje odwiedzony w wyniku wywołania przeszukiwania \( DFS \) podczas przeglądania listy sąsiedztwa \( v \). Wówczas jednak \( u \) znajdzie się w poddrzewie przeszukiwania o korzeniu w \( v \). Ponieważ \( u \) jest na liście \( v \), do takiego wywołania dojść musi – sprzeczność z założeniem, że \( u \), \( v \) nie są w relacji potomek-przodek.
Numeracja w głąb pozwala łatwo sprawdzić, czy dwa różne wierzchołki \( u \), \( v \) są w relacji przodek-potomek w drzewie przeszukiwania w głąb. Załóżmy, że \( nr[u] < nr[v] \).
Wierzchołek \( u \) jest przodkiem wierzchołka \( v \) w drzewie przeszukiwania w głąb wtedy i tylko wtedy, gdy \( nr[u] < nr[v] \le nr[u] + d[u] \), gdzie \( d[u] \) jest liczbą wierzchołków w poddrzewie o korzeniu w \( u \).
Pokażemy teraz, w jaki sposób zastosować przeszukiwanie w głąb do wyznaczenia wszystkich mostów grafie. Przypomnijmy, że mostem w spójnym grafie \( G \) nazywamy każdą krawędź, której usunięcie rozspójnia ten graf. Zauważmy, że bardzo łatwo wyznaczyć wszystkie mosty w czasie \( O(m(n+m)) \). Wystarczy dla każdej krawędzi sprawdzić w czasie liniowym, czy usunięcie tej krawędzi zwiększa liczbę spójnych składowych w grafie. Przeszukiwanie w głąb pozwala rozwiązać ten problem w czasie liniowym. Zanim przedstawimy stosowny algorytm, spróbujmy scharakteryzować mosty z wykorzystaniem drzewa przeszukiwania w głąb i numeracji w głąb.
Spostrzeżenie 1
Jeśli krawędź jest mostem w grafie, jest krawędzią każdego drzewa rozpinającego tego grafu.
Rozważmy drzewo przeszukiwania w głąb i niech \( u-v \) będzie krawędzią w tym drzewie. Załóżmy także, że \( u \) jest ojcem \( v \).
Spostrzeżenie 2
Krawędź \( u-v \) jest mostem wtedy i tylko wtedy, gdy żadna krawędź niedrzewowa nie łączy wierzchołka z poddrzewa o korzeniu w \( v \) z właściwym przodkiem \( v \). Innymi słowy wtedy i tylko wtedy, gdy oba końce każdej krawędzi niedrzewowej leżą w poddrzewie o korzeniu w \( v \), jeśli tylko jeden z tych końców jest w tym poddrzewie.
Spróbujemy warunek ze spostrzeżenia 2 wyrazić trochę inaczej. Dla każdego wierzchołka \( v \) niech \( low[v] \) będzie najmniejszym numerem w głąb wierzchołka, który można osiągnąć z \( v \) ścieżką składającą z krawędzi drzewowych z poddrzewa o korzeniu w \( v \) i zakończoną co najwyżej jedną krawędzią niedrzewową prowadzącą poza to poddrzewo. Funkcję \( low \) można rekurencyjnie zdefiniować w następujący sposób:
\( low[v] = \min(\{nr[v]\}\cup \{nr[u]: u-v \mbox{ jest krawędzią niedrzewową }\} \cup \{low[u]: u \mbox{ jest synem } v \mbox{ w drzewie przeszukiwania w głąb}\}) \)
Spostrzeżenie 3
Niech \( v-u \) będzie krawędzią drzewa przeszukiwania w głąb taką, że \( v \) jest ojcem \( u \) w tym drzewie. Wówczas krawędź \( v-u \) jest mostem wtedy i tylko wtedy, gdy \( low[u] > nr[v] \).
Powyższe spostrzeżenia pozwalają już na zaproponowanie liniowego algorytmu wyznaczania mostów w spójnym grafie \( G \). Algorytm ten zapiszemy za pomocą rekurencyjnej procedury \( DFS-Bridges(v) \).
Algorytm Mosty
procedure DFS-Bridges(v, ojciec_v) begin visited[v] :=TRUE; ostnr := ostnr + 1; nr[v] := ostnr; low[v] := ostnr; for each u in L[v] do begin if u <> ojciec_v then begin if NOT visited[u] then begin DFS-Bridges(u, v); low[v] := min(low[v],low[u]); end else low[v] := min(low[v],nr[u]); end; if low[v] = nr[v] then krawędź v-ojciec_v jest mostem; end; end;
Żeby wyznaczyć wszystkie mosty wystarczy wywołać \( DFS-Bridges(s) \) dla dowolnego wierzchołka \( s \). Złożoność wyznaczania mostów jest asymptotycznie taka sama jak zwykłego przeszukiwania grafu, czyli \( O(n+m) \).