Algorytmy i struktury danych/Przeszukiwanie grafów

From Studia Informatyczne

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:

1 for each v \in V do
2 begin
3   current[v] := pierwszy wierzchołek na liście sąsiedztwa L[v];
4   visited[v] := FALSE; //markujemy, że wierzchołek v nie był jeszcze odwiedzony
5 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


1  procedure Search(s);
2  begin
3    S := \{s\};
4    visited[s] :=TRUE; //markujemy s jako odwiedzony
5    while S \ne \emptyset do
6    begin
7      u := Get(S);
8      if current[u] \ne NIL then 
9      //jeśli nie wyczerpaliśmy całej listy sąsiadów wierzchołka u
10     begin
11     //pobierz kolejny wierzchołek z listy sąsiadów i przejdź do następnego
12     // wierzchołka na liście
13       v := current[u]; current[u] := next(current[u]);
14       if NOT visisted[v] then //jeśli v nie był jeszcze odwiedzony
15   begin
16     visited[v] := TRUE;// markujemy v jako odwiedzony
17     Insert(S,v) //wstaw v do zbioru S
18       end
19     end
20     else //wszystkie krawędzie opuszczające u zostały już zbadane
21       Delete(S,u)     
22    end
23  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.

1 Inicjacja przeszukiwania grafu.
2 for each v \in V do
3   if NOT visited[v] then
4     //odkryta została nowa spójna składowa zawierająca wierzchołek v
5     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.

Przeszukiwanie wszerz

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.

Przeszukiwanie w głąb

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


1  procedure DFS(v);
2  //v jest nowo odkrytym wierzchołkiem
3  begin
4    //markujemy v jako odwiedzony
5    visited[v] :=TRUE;
6    //wierzchołkowi v nadajemy kolejny numer
7    ost{nr} := ost{nr} + 1; nr[v] := ost{nr}; 
8    //przeglądamy listę sąsiedztwa v i dla każdego nowo odkrytego 
9    //wierzchołka wywołujemy procedurę DFS
10   for each u \in L[v] do
11     if NOT visited[u] then
12       DFS(u)
13 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


1  procedure DFS-Bridges(v);
2  //v jest nowo odkrytym wierzchołkiem
3  begin
4    //markujemy v jako odwiedzony
5    visited[v] :=TRUE;
6    //wierzchołkowi v nadajemy kolejny numer
7    ostnr := ostnr + 1; nr[v] := ostnr;
8    //inicjacja low[v] 
9    low[v] := ostnr;
10   //przeglądamy listę sąsiedztwa v i dla każdego nowo odkrytego 
11   //wierzchołka wywołujemy procedurę DFS; dokonujemy też 
12   //aktualizacji low[v]
13   for each u \in L[v] do
14     if NOT visited[u] then
15     begin  
16       DFS-Bridges(u);
17       low[v] := \min(low[v],low[u]);
18       if low[u] > nr[v] then
19         krawędź v-u jest mostem; 
20     end
21     else
22       low[v] := \min(low[v],nr[u])
23 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).