Algorytmy grafowe - 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), 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.

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

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)$ .

Informatyka MIMUW