Sposoby reprezentacji i wykorzystanie grafów. Algorytmy DFS, BFS

Data dodania: 2011-09-18, Autor: michalrum, Dodał: Karol, Wyświetleń: 1021

Grafy

Grafy mogą służyć do poglądowego przedstawienia złożonych sytuacji i relacji z którymi spotykamy się w życiu. Jest to bardzo wygodny i stosunkowo prosty w implementacji sposób przedstawienia często skomplikowanych zależności.

Na początek należy zdefiniować i wyjaśnić kilka podstawowych pojęć związanych z teorią grafów:

• Graf-zestaw węzłów i połączeń między węzłami.
• Węzeł(wierzchołek)-węzły grafu reprezentują obiekty o określonych własnościach.
• Krawędź-ustanawia związek pomiędzy dwoma węzłami.
• Węzły przyległe(sąsiedzi)-węzły, pomiędzy którymi istnieje krawędź (w grafie skierowanym-digrafie, istotny jest kierunek krawędzi)
• Rząd węzła(stopień)-liczba węzłów przyległych do niego, oznaczmy deg(v), v-węzeł
• Węzeł izolowany-węzeł rzedu 0
• Krawędzie przyległe- krawędzie posiadające wspólny węzeł
• Ścieżka- lista węzłów na które natrafimy przemieszczając się z węzła do węzła.

Dla grafu na powyższym rysuku ABCD i ACD są dwiema ścieżkami od węzła A do D.

• Graf spójny-pomiędzy dowolną parą węzłów istnieje przynajmniej jedna ścieżka;
• Ścieżka prosta-ścieżka która nie prowadzi przez żaden węzeł więcej niż raz.
• Cykl-ścieżka prosta która ma swój początek i koniec w tym samym węźle.
• Graf ważony-każda krawędź wiąże się z liczbą rzeczywistą, nazywaną ‘wagą’ lub ‘kosztem’ krawędzi.

Dla dowolnego grafu mamy

gdzie m-liczba krawędzi grafu, V(G)-zbiór wierzchołków grafu G.

Reprezentacja grafów:

Macierz połączeń:

Jest to kwadratowa macierz o rozmiarze równym liczbie węzłów w grafie, nazwijmy ją sobie A. Jeżeli w grafie istnieje krawędź łącząca węzeł i z węzłem j, to A[i,j]=1, w przeciwnym wypadku A[i,j]=0. Dla digrafu macierz ta nie jest symetryczna, natomiast dla grafu nieskierowanego A[i,j]=A[j,i], dla i!=j.

Dla grafu o n wierzchołkach macierz zawiera n^2 elementów. Zaletą danej metody jest natychmiastowy dostęp do elementu A[i,j], prostota implementacji. Metoda ta staje się jednak nieefektywna pamięciowo, dla grafów o dużej liczbie wierzchołków i małej liczbie połączeń pomiędzy nimi. W przypadku grafu ważonego binarne wartości 0,1 zostają zastąpione wagą odpowiedniej krawędzi-takie rozwiązanie można zastosować np. przy implementacji algorytmu Dijkstry.

Macierz indydencji:

Dla danego grafu G=(V,E), V-zbiór wierzchołków, E- zbiór krawędzi, macierz ta wymaga |V|*|E| bitów pamięci, jest ona jednak często stosowana przy algorytmicznym rozpatrywaniu obwodów elektrycznych i układów przełączających.

Dla grafu przedstawionego powyżej, macierz incydencji przyjmuje postać:

Lista sąsiadów:

Dla grafu z rysunku powyżej, lista sąsiadów przyjmyje postać:

struct wezel
{
  int nr;
  int *sasiedzi;
  int ilosc;
}

Przykładowa struktura do przechowywania listy sąsiadów danego wierzchołka. Dla każdego węzła dynamicznie tworzymy tablice zawierającą numery sąsiadów. Zmienna ‘ilosc’ zawiera informacje o ilości sąsiadów, dzięki czemu tablica sąsiadów być modyfikowana podczas czytania wejścia funkcja realloc(); Metoda ta zapewnia optymalne wykorzystanie pamięci, czas dostępu również jest zadowalający czasowo, dla grafów rzadkich.

struct wezel
{
  int nr;
  struct wezel *sasiedzi;
}

Drugim wariantem listy sąsiadów jest pamiętanie jedynie wskaźników na sąsiednie wierzchołki. Nie musimy już wtedy znać ilości sąsiadów. Po prostu podczas czytania połączeń dodajemy wskaźniki na do listy, ostatni zawsze ustawiamy na NULL. Wtedy połączenia można zilustrować rysukniem:

Oprócz wyżej opisanych metod do reprezentacji grafów stosuje się listy dwukierunkowe przyległych węzłów, oraz jedno-lub dwu kierunkowe listy krawędzi. Tak naprawdę wybór sposobu reprezentacji uzależniony jest od konkretnego problemu do rozwiązania.

Poniżej postaram się omówić dwa algorytmy przeszukiwania grafów:

DFS Depth First Search

Inna nazwa to ‘przeszukiwanie z nawrotami’, która to wynika wprost z działania metody. W metodzie tej oznaczamy węzły jako ‘odwiedzone’ i ‘nieodwiedzone’. Można to zrealizować za pomocą tablicy boolowskiej, lub tez dodać do struktury węzła parametr-zmienna oznaczający odwiedzenie bądź nie. Poniżej przedstawiam pseudokod działania algorytmu:

Procedura pomocnicza 'wizytacja' (A)
  //Q-oznacza węzeł
  jeżeli węzeł  A nie jest odwiedzony
    zaznacz węzeł A jako odwiedzony;
    dla każdego węzła X przyległego do A wykonaj: 
        wizytacja(x);

procedura 'przeszukiwanie zstępujące'
  //oznacz wszystkie węzły jako nieodwiedzone
  wybierz dowolny węzeł X grafu i wykonaj:
    wizytacja(X);

Przeszukiwanie DFS zilustruje na powyższym przykładzie grafu;

Startujemy z węzła A

• odwiedzamy A
• odwiedzamy B, odkładamy na bok D
• odwiedzamy C, odkładamy na bok D, E, F
• odwiedzamy F
• zabieramy z boku F-i nic już z nim nie robimy
• zabieramy z boku E i odwiedzamy E
• odwiedzamy D
• zabieramy z boku D-i nic już z nim nie robimy
• zamieramy z boku D-i nic już z nim nie robimy

Punkty 5,8,9 to czynności jałowe-dla dużych grafów czynności takie mogą stanowić poważną stratę czasu, co jest minusem przedstawionego algorytmu.

BFS Bread-First Search

Przeszukiwanie grafu wszerz

Algorytm ten również korzysta z mechanizmu oznaczania wierzchołków jako ‘odwiedzone’ i ‘nieodwiedzone’, ponadto wykorzystuje on strukture kolejki, nazwijmy ją Q

Pseudokod algorytmu:

Utwórz kolejkę Q i zainicjuj ją jako pustą
Oznacz wszystkie węzły jako nieodwiedzone

//załóżmy ze startujemy z węzła A...
Oznacz węzeł A jako odwiedzony i dodaj do kolejki Q

Wykonuj następujące kroki, dopóki kolejka nie jest pusta:
    Pobierz węzeł z kolejki (nazwijmy go X)
    Odwiedź te węzły przyległe do X, które jeszcze nie zostały odwiedzone

Dodaj do kolejki wszystkie węzły przyległe do X;

Zwolnij obiekt Q;

Ścieżka odwiedzin dla przykładu zilustrowanego powyżej: A,B,D,E,C,F.

Algorytm BFS jest wolny od problemów które występowały przy DFS, nie ma tu jałowych wywołań, co czyni algorytm szybszym niż DFS.

Mogę dodać że zaimplementowane pseudokody z powodzeniem rozwiązują zadanie TDBFS na www.spoj.sphere.pl. Ja polecam spróbowac.

Grafów można używać jako obiekty reprezentacji przy wielu problemach:

• problem kojarzenia małżeństw
• problem znajdowania najkrótszej drogi, algorytm Dijkstry, Floyda-Warshalla
• wyznaczanie drzew spinającego, algorytm Prima, Kruskala
• problem komiwojażera
• strategie minimaksowe i wartościowanie gier

Każdemu z tych problemów można by poświęcić osobny artykuł, wiec ograniczę się do wymienienia tych problemów.