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

Ćwiczenia

Zadanie 1

Pokaż, w jaki sposób sprawdzić w czasie liniowym, czy graf jest grafem dwudzielnym:


a) za pomocą przeszukiwania wszerz,
b) z wykorzystaniem przeszukiwania w głąb.

Zadanie 2

Niech \( G=(V,E) \) będzie grafem spójnym. Wierzchołkiem rozdzielającym w grafie \( G \) nazywamy każdy wierzchołek, którego usunięcie rozspójnia \( G \). Zaadaptuj algorytm wykrywania mostów grafie do znajdowania wszystkich wierzchołków rozdzielających.

Zadanie 3

Graf spójny bez wierzchołków rozdzielających nazywamy grafem dwuspójnym. Dwuspójną składową grafu G nazywam każdy jego maksymalny (w sensie zawierania) dwuspójny podgraf.
a) Udowodnij, że każda krawędź grafu należy do dokładnie jednej dwuspójnej składowej.
b) Zaprojektuj algorytm, który w czasie liniowym policzy wszystkie dwuspójne składowe danego (przez listy sąsiedztw), spójnego grafu, tzn. podzieli zbiór wszystkich krawędzi na podzbiory odpowiadające poszczególnym dwuspójnym składowym.

Zadanie 4

Dotychczas rozważaliśmy tylko grafy nieskierowane. Zaproponuj sposób reprezentacji grafu skierowanego za pomocą list sąsiedztw.

Zadanie 5

Powiemy, że graf skierowany jest silnie spójny, jeśli dla każdej pary wierzchołków \( u \), \( v \) istnieją skierowane ścieżki z \( u \) do \( v \) i z \( v \) do \( u \). Zaprojektuj algorytm, który w czasie \( O(n+m) \) sprawdza, czy dany graf jest grafem silnie spójnym.

Zadanie 6

Zaproponuj algorytm, który w czasie liniowym zorientuje krawędzie grafu dwuspójnego w taki sposób, żeby otrzymany graf był silnie spójny.