Algorytmy i struktury danych/Przeszukiwanie grafów

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 , w którym przechowujemy odwiedzane wierzchołki i których sąsiedztwa nie są jeszcze do końca zbadane. Zakładamy, że na zbiorze wykonywane są następujące operacje:

: wstaw do zbioru wierzchołek ;

: funkcja, której wynikiem jest (dowolny) wierzchołek z , wywoływana tylko wtedy, gdy ;

: usuń z wierzchołek (zazwyczaj będzie to wierzchołek .

Informacje o tym, które wierzchołki zostały już odwiedzone, będziemy przechowywać w tablicy logicznej . Wartością jest PRAWDA (TRUE) wtedy i tylko wtedy, gdy wierzchołek został już odwiedzony. Do przechodzenia list sąsiedztw posłuży nam tablica . Wartością jest pierwszy wierzchołek na liście - sąsiad - który nie był jeszcze oglądany od strony , co oznacza że krawędź opuszczająca w kierunku tego sąsiada nie została jeszcze zbadana.

Inicjacja każdego przeszukiwania wygląda następująco:

1 for each  do
2 begin
3    := pierwszy wierzchołek na liście sąsiedztwa ;
4    FALSE; //markujemy, że wierzchołek  nie był jeszcze odwiedzony
5 end;

Załóżmy, że przeszukiwanie grafu rozpoczynamy z wybranego wierzchołka . Wówczas schemat przeszukiwania z można zapisać następująco.

Algorytm Przeszukiwanie grafu - algorytm generyczny


1  procedure Search(s);
2  begin
3    ;
4    TRUE; //markujemy  jako odwiedzony
5    while  do
6    begin
7      ;
8      if  NIL then 
9      //jeśli nie wyczerpaliśmy całej listy sąsiadów wierzchołka 
10     begin
11     //pobierz kolejny wierzchołek z listy sąsiadów i przejdź do następnego
12     // wierzchołka na liście
13       ; ;
14       if NOT  then //jeśli  nie był jeszcze odwiedzony
15   begin
16      TRUE;// markujemy  jako odwiedzony
17      //wstaw  do zbioru 
18       end
19     end
20     else //wszystkie krawędzie opuszczające  zostały już zbadane
21            
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 o wartościach w zbiorze wierzchołków taka, że wtedy i tylko wtedy, gdy i należą do tej samej spójnej składowej.

Zauważmy, że problem spójności bardzo łatwo rozwiązać przy użyciu procedury . Jeśli przeszukiwanie rozpoczynamy od nieodwiedzonego wierzchołka , to w wyniku wykonania zostaną odwiedzone wszystkie wierzchołki w grafie osiągalne z . Innymi słowy odwiedzona zostanie cała spójna składowa zawierająca . Jeśli dla każdego nowo odwiedzanego wierzchołka wykonamy przypisanie , po zakończeniu przeszukiwania spójnej składowej zawierającej , wartość każdego wierzchołka w tej składowej będzie właśnie równa . Jedyne miejsce, w którym musimy zmieniać procedurę jest wiersz 16. Nowy wiersz 16 powinien mieć postać:

16 TRUE; ;

Tak zmodyfikowaną procedurę nazwiemy z angielskiego Search Connected Components (czyli wyszukaj spójne składowe). Oto algorytm obliczania spójnych składowych z wykorzystaniem procedury .

1 Inicjacja przeszukiwania grafu.
2 for each  do
3   if NOT  then
4     //odkryta została nowa spójna składowa zawierająca wierzchołek 
5     
   

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 jest wykonywana w czasie stałym. Zauważmy, że każdy wierzchołek jest dokładnie raz wstawiany do zbioru - w momencie odkrycia go jako nieodwiedzonego - i dokładnie raz jest usuwany ze zbioru - 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 . 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 . Z naszej analizy wynika, że problem spójnych składowych można rozwiązać w czasie , czyli liniowym ze względu na rozmiar grafu.

W dalszym ciągu tego wykładu będziemy rozważali tylko grafy spójne. Niech będzie grafem spójnym, a wyróżnionym wierzchołkiem w . Zanalizujmy raz jeszcze wykonanie procedury dla grafu . Dla każdego wierzchołka niech będzie wierzchołkiem z którego wierzchołek zostaje odwiedzony, tzn. zostaje zamarkowany jako odwiedzony w wierszu 16, gdy zostaje odkryty na liście sąsiedztwa . Nietrudno zauważyć, że graf jest drzewem rozpinającym grafu . Jeśli każdą krawędź tego drzewa zorientujemy od do , otrzymamy drzewo o korzeniu , 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 wyznaczają dla każdego wierzchołka jedyną ścieżkę w drzewie łączącą z korzeniem .

Dotychczas nic nie mówiliśmy o implementacji zbioru . Rozważymy dwie naturalne implementacje. W pierwszej z nich zbiór jest kolejką typu FIFO. W tej implementacji wynikiem funkcji jest ten wierzchołek ze zbioru , który przebywa w nim najdłużej. W drugiej implementacji zbiór jest stosem, a wynikiem jest wierzchołek przebywający w najkrócej, czyli ostatnio wstawiony. Kolejkę i stos łatwo zaimplementować w taki sposób, żeby każda z wymaganych przez nas operacji na zbiorze 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 użyjemy kolejki? Zauważmy, że do zbioru wierzchołki są wstawiane w następującej kolejności. Najpierw pojawia się w wyróżniony wierzchołek . Wierzchołek 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 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 w kolejce pojawią się wszyscy sąsiedzi sąsiadów , którzy nie sąsiadują bezpośrednio z . W dalszej kolejności w zbiorze pojawią się sąsiedzi sąsiadów sąsiadów , sąsiedzi sąsiadów sąsiadów sąsiadów , itd. Podzielmy zbiór wierzchołków grafu na warstwy . Warstwa składa się tylko z wierzchołka . Warstwa to sąsiedzi . Warstwa to te wierzchołki grafu, które sąsiadują z co najmniej jednym wierzchołkiem z warstwy i nie należą do żadnej z warstw poprzednich, czyli i . Do warstwy należą wierzchołki sąsiadujące z co najmniej jednym wierzchołkiem z warstwy poprzedniej () i nie należą do warstw o numerach mniejszych od 3, itd. Nietrudno zauważyć, że -ta warstwa składa się ze wszystkich tych wierzchołków, których odległość (długość najkrótszej ścieżki) od w grafie wynosi dokładnie . Dla każdego wierzchołka wskaźniki wyznaczają najkrótszą ścieżkę łączącą z . 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 . 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 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ę , w której dodatkowo numerujemy wierzchołki w kolejności odwiedzania. W tym celu użyjemy globalnej zmiennej , której wartością jest ostatnio nadany numer. Zmienną inicjujemy na 0. Otrzymaną numerację będziemy nazywali numeracją w głąb.

Algorytm Przeszukiwanie w głąb


1  procedure ;
2  // jest nowo odkrytym wierzchołkiem
3  begin
4    //markujemy  jako odwiedzony
5    TRUE;
6    //wierzchołkowi  nadajemy kolejny numer
7    ; ; 
8    //przeglądamy listę sąsiedztwa  i dla każdego nowo odkrytego 
9    //wierzchołka wywołujemy procedurę 
10   for each  do
11     if NOT  then
12       
13 end;

Jeśli chcemy przeszukać graf poczynając od wierzchołka , wystarczy wywołać , inicjując wcześniej tablice i oraz zmienną . Zauważmy, że krawędź zaliczamy do drzewa przeszukiwania (w głąb), jeśli po wejściu do wierzchołka odkrywamy, że wierzchołek na liście sąsiedztwa 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ź taka, że wierzchołki , nie są w relacji potomek-przodek. Bez straty ogólności możemy przyjąć, że zostaje odwiedzony wcześniej niż . Załóżmy, że zostaje odwiedzony w wyniku wywołania przeszukiwania podczas przeglądania listy sąsiedztwa . Wówczas jednak znajdzie się w poddrzewie przeszukiwania o korzeniu w . Ponieważ jest na liście , do takiego wywołania dojść musi – sprzeczność z założeniem, że , nie są w relacji potomek-przodek.

Numeracja w głąb pozwala łatwo sprawdzić, czy dwa różne wierzchołki , są w relacji przodek-potomek w drzewie przeszukiwania w głąb. Załóżmy, że .

Wierzchołek jest przodkiem wierzchołka w drzewie przeszukiwania w głąb wtedy i tylko wtedy, gdy , gdzie jest liczbą wierzchołków w poddrzewie o korzeniu w .

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 nazywamy każdą krawędź, której usunięcie rozspójnia ten graf. Zauważmy, że bardzo łatwo wyznaczyć wszystkie mosty w czasie . 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 będzie krawędzią w tym drzewie. Załóżmy także, że jest ojcem .

Spostrzeżenie 2

Krawędź jest mostem wtedy i tylko wtedy, gdy żadna krawędź niedrzewowa nie łączy wierzchołka z poddrzewa o korzeniu w z właściwym przodkiem . Innymi słowy wtedy i tylko wtedy, gdy oba końce każdej krawędzi niedrzewowej leżą w poddrzewie o korzeniu w , 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 niech będzie najmniejszym numerem w głąb wierzchołka, który można osiągnąć z ścieżką składającą z krawędzi drzewowych z poddrzewa o korzeniu w i zakończoną co najwyżej jedną krawędzią niedrzewową prowadzącą poza to poddrzewo. Funkcję można rekurencyjnie zdefiniować w następujący sposób:

Spostrzeżenie 3

Niech będzie krawędzią drzewa przeszukiwania w głąb taką, że jest ojcem w tym drzewie. Wówczas krawędź jest mostem wtedy i tylko wtedy, gdy .


Powyższe spostrzeżenia pozwalają już na zaproponowanie liniowego algorytmu wyznaczania mostów w spójnym grafie . Algorytm ten zapiszemy za pomocą rekurencyjnej procedury .

Algorytm Mosty


1  procedure ;
2  // jest nowo odkrytym wierzchołkiem
3  begin
4    //markujemy  jako odwiedzony
5    TRUE;
6    //wierzchołkowi  nadajemy kolejny numer
7    ; ;
8    //inicjacja  
9    ;
10   //przeglądamy listę sąsiedztwa  i dla każdego nowo odkrytego 
11   //wierzchołka wywołujemy procedurę ; dokonujemy też 
12   //aktualizacji 
13   for each  do
14     if NOT  then
15     begin  
16       ;
17       ;
18       if  then
19         krawędź  jest mostem; 
20     end
21     else
22       
23 end;   

Żeby wyznaczyć wszystkie mosty wystarczy wywołać dla dowolnego wierzchołka . Złożoność wyznaczania mostów jest asymptotycznie taka sama jak zwykłego przeszukiwania grafu, czyli .