Algorytmy i struktury danych/Przeszukiwanie grafów

Przeszukiwanie grafów

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), to 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$, zakładamy, funkcja $Get$ jest wywoływana tylko wtedy, gdy $S\ne \mathrm{\varnothing }$

$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]$ będzie PRAWDA (TRUE) wtedy i tylko wtedy, gdy wierzchołek $v$ zostanie już odwiedzony. Do przechodzenia list sąsiedztw posłuży nam tablica $current[1..n]$. Wartością $current[v]$ będzie 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  Search(s);
2  begin
3    $S:=\{s\}$;
4    $visited[s]:=$TRUE; //markujemy $s$ jako odwiedzony
5    while $S\ne \mathrm{\varnothing }$ 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. Dodatkowo żądamy, żeby do tej składowej należał także wierzchołek $v$.

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$, to 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 zmienić 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 nieodwiedzony - i dokładnie raz jest usuwany ze zbioru $S$ - po obejrzeniu 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, to nic nie robimy, natomiast, jeśli nie był odwiedzony, to markujemy go jako odwiedzony i wstawiamy do zbioru $S$. Tak więc obliczenia związane z przeglądaniem sąsiedztw wierzchołków zajmują 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$, to otrzymamy drzewo z korzeniem 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. Zarówno kolejkę, jak 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. Do tego 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,\dots$. 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ę dokładnie z 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]],\dots$ 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, ze 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 policzyć w czasie liniowym o ile tylko 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’’.

1  $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    $os{t}_{n}r:=os{t}_{n}r+1$; $nr[v]:=os{t}_{n}r$; 
6    //przeglądamy listę sąsiedztwa $v$ i dla każdego nowo odkrytego wierzchołka wywołujemy procedurę $DFS$
7    ’’’for each’’’ $u\in L[v]$ ’’’do’’’
8      ’’’if’’’ $NOTvisited[u]$ ’’’then’’’
9        $DFS(u)$
10 ’’’end’’’

Jeśli chcemy przeszukać graf poczynając od wierzchołka $s$, to wystarczy wywołać $DFS(s)$, oczywiście inicjując wcześniej tablice $visited$ i $current$, oraz zmienną $os{t}_{n}r$. Zauważmy, że do drzewa przeszukiwania (w głąb) zaliczamy każdą taką krawędź $(v,u)$, że po wejściu do wierzchołka $v$ odkryjemy, ż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ź $u-v$ i taka, że wierzchołki $u$, $v$ nie są w relacji potomek-przodek. Bez straty ogólności możemy przyjąć, ze $u$ zostaje odwiedzony wcześniej niż $v$. Załóżmy, że $v$ zostaje odwiedzony w wyniku wywołania przeszukiwania $DFS$ podczas przeglądania listy sąsiedztwa $u$. Wówczas jednak $v$ znajdzie się w poddrzewie przeszukiwania o korzeniu w $u$. Ponieważ $v$ jest na liście $u$, to 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]<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 wyznaczanie 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, ze 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ększyło 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 i numeracji w głąb.

Spostrzeżenie 1

Jeśli krawędź jest mostem w grafie, to 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ńczonych 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\text{ jest krawędzią niedrzewową }\}\cup \{low[u]:u\text{ jest synem }v\text{ w drzewie przeszukiwania w głąb}\})$

Spostrzeżenie 3

Niech $v-u$ będzie krawędzią drzewa przeszukiwania w głąb i 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)$.

1  $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    $os{t}_{n}r:=os{t}_{n}r+1$; $nr[v]:=os{t}_{n}r$;
8    //inicjacja $low[v]$ 
9    $low[v]:=os{t}_{n}r$;
10   //przeglądamy listę sąsiedztwa $v$ i dla każdego nowo odkrytego 
11   //wierzchołka wywołujemy procedurę $DFS$; dokonujemy też aktualizacji $low[v]$
11   ’’’for each’’’ $u\in L[v]$ ’’’do’’’
12     ’’’if’’’ $NOTvisited[u]$ ’’’then’’’
13     ’’’begin’’’  
14       $DFS-Bridges(u)$;
15       $low[v]:=\min (low[v],low[u])$;
16       ’’’if’’’ $low[u]>nr[v]$ ’’’then’’’
17         krawędź $v-u$ jest mostem; 
16     ’’’end’’’
17     ’’’else’’’
18       $low[v]:=\min (low[v],nr[u])$
19 ’’’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)$.