Ogólnie

 

Na poczatku definicja grafu, potem kilka algorytmów:

  • Problem najkrótszej ścieżki
  • Minimalne drzewo rozpinające
  • Przeszukiwanie grafu
  • Problem komiwojażera

Graf

 

Graf to – w uproszczeniu – zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków. Grafy to podstawowy obiekt rozważań teorii grafów.

Wierzchołki grafu zwykle są numerowane i czasem stanowią reprezentację jakichś obiektów, natomiast krawędzie mogą wówczas obrazować relacje między takimi obiektami. Krawędzie mogą mieć wyznaczony kierunek, a graf zawierający takie krawędzie jest grafem skierowanym. Krawędź może posiadać także wagę, to znaczy przypisaną liczbę, która określa na przykład odległość między wierzchołkami (jeśli na przykład graf jest reprezentacją połączeń między miastami). W grafie skierowanym wagi mogą być zależne od kierunku przechodzenia przez krawędź (np. jeśli graf reprezentuje trud poruszania się po jakimś terenie, to droga pod górkę będzie miała przypisaną większą wagę niż z górki).

Problem najkrótszej ścieżki

 

Problem najkrótszej ścieżki jest zagadnieniem szczególnie istotnym w informatyce. Polega on na znalezieniu w grafie ważonym najkrótszego połączenia pomiędzy danymi wierzchołkami. Szczególnymi przypadkami tego problemu są problem najkrótszej ścieżki od jednego wierzchołka do wszystkich innych oraz problem najkrótszej ścieżki pomiędzy wszystkimi parami wierzchołków.

Okazuje się, że żeby znaleźć najkrótszą ścieżkę pomiędzy dwoma wierzchołkami grafu trzeba (w pesymistycznym przypadku) znaleźć najkrótsze ścieżki od wierzchołka wyjściowego do wszystkich innych wierzchołków. Problem najkrótszej ścieżki od jednego z wierzchołków do wszystkich innych można więc zobrazować jako problem znalezienia najkrótszej drogi pomiędzy dwoma miastami. W takim wypadku wierzchołkami grafu są skrzyżowania dróg, krawędziami – drogi, a wagi krawędzi odwzorowują długość danego odcinka drogowego. Do znalezienia najkrótszej ścieżki pomiędzy dwoma wierzchołkami zazwyczaj używane są algorytmy:

  • Dijkstry (przy założeniu, że w grafie nie ma wag ujemnych)
    Mając dany graf z wyróżnionym wierzchołkiem (źródłem) algorytm znajduje odległości od źródła do wszystkich pozostałych wierzchołków. Łatwo zmodyfikować go tak, aby szukał wyłącznie ścieżki do jednego ustalonego wierzchołka, po prostu przerywając działanie w momencie dojścia do wierzchołka docelowego.
    Algorytm Dijkstry jest przykładem algorytmu zachłannego.
    Dijkstra(G,w,s):
       dla każdego wierzchołka v w V[G] wykonaj
          d[v] := nieskończoność
          poprzednik[v] := niezdefiniowane
       d[s] := 0
       Q := V
       dopóki Q niepuste wykonaj
          u := Zdejmij_Min(Q)
          dla każdego wierzchołka v – sąsiada u wykonaj
             jeżeli d[v] > d[u] + w(u, v) to
                d[v] := d[u] + w(u, v)
                poprzednik[v] := u
  • Bellmana-Forda
  • A*, używający heurystyki
Drugi szczególny przypadek problemu najkrótszej ścieżki występuje, gdy chcemy znaleźć najkrótsze ścieżki pomiędzy każdą parą wierzchołków. Oczywiście możliwe jest zrobienie tego dla każdego wierzchołka używając algorytmu znajdującego najkrótszą ścieżkę od jednego wierzchołka do wszystkich innych, jednak metoda ta okazuje się w praktyce niezbyt efektywna. Najkrótsze ścieżki pomiędzy wszystkimi wierzchołkami znajdują m.in. algorytmy:

  • Floyda-Warshalla
  • Johnsona

Minimalne drzewo rozpinające

 

Drzewem rozpinającym (ang. Spanning Tree) grafu G nazywamy drzewo, które zawiera wszystkie wierzchołki grafu G, zaś zbiór krawędzi drzewa jest podzbiorem zbioru krawędzi grafu.
Konstrukcja drzewa rozpinającego polega na usuwaniu z grafu tych krawędzi które należą do cykli.

Minimalne drzewo rozpinające (ang. MST, Minimum Spanning Tree ) jest to drzewo rozpinające danego grafu o najmniejszej z możliwych wag, tj. takie, że nie istnieje dla tego grafu inne drzewo rozpinające o mniejszej sumie wag krawędzi.
Istnieją trzy deterministyczne algorytmy o złożoności liniowo-logarytmicznej znajdujące dla zadanego grafu minimalne drzewo rozpinające. Są to:

  • algorytm Prima (nazywany też algorytmem Dijkstry-Prima)
  • algorytm Kruskala
    Algorytm Kruskala wyznacza minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład algorytmu zachłannego.

    • Utwórz las L z wierzchołków oryginalnego grafu – każdy wierzchołek jest na początku osobnym drzewem.
    • Utwórz zbiór S zawierający wszystkie krawędzie oryginalnego grafu.
    • Dopóki S nie jest pusty:
      • Wybierz i usuń z S krawędź o minimalnej wadze.
      • Jeśli krawędź ta łączyła dwa różne drzewa, to dodaj ją do lasu L, tak aby połączyła dwa odpowiadające drzewa w jedno.
      • W przeciwnym wypadku odrzuć ją.
    Po zakończeniu algorytmu L jest minimalnym drzewem rozpinającym.

Przeszukiwanie grafu

 

Przeszukiwanie grafu lub inaczej przechodzenie grafu to czynność polegająca na odwiedzeniu w jakiś usystematyzowany sposób wszystkich wierzchołków grafu w celu zebrania potrzebnych informacji. Często podczas przejścia grafu rozwiązujemy już jakiś problem, ale przeważnie jest to tylko wstęp do wykonania właściwego algorytmu.

Powszechnie stosuje się dwie podstawowe metody przeszukiwania grafów:

  • przeszukiwanie wszerz (BFS)
    Algorytm zaczyna od korzenia i odwiedza wszystkie połączone z nim węzły. Następnie odwiedza węzły połączone z tymi węzłami i tak dalej, aż do odnalezienia celu.
    funkcja przeszukiwanie_wszerz (Start, Cel)
        dodaj_do_kolejki(Kolejka, Start)
        dopóki nie_pusta(Kolejka)
            Wierzchołek:= pobierz_z_kolejki(Kolejka)
            jeżeli Wierzchołek = Cel
                zwróć Wierzchołek /* i zakończ funkcję */
            dla każdego Syna w Wierzchołek
               jeżeli nie_odwiedzony(Syn) 
                  zapamiętaj_że_odwiedzony(Syn)
                  dodaj_do_kolejki(Kolejka, Syn)

  • przeszukiwanie w głąb (DFS)
    Przeszukiwanie zaczyna się od korzenia i porusza się w dół do samego końca gałęzi, po czym wraca się o jeden poziom i próbuje kolejne gałęzie itd.
    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);
Odrębnym zagadnieniem jest przechodzenie drzew, zwłaszcza binarnych które jest niewątpliwie przeszukiwaniem grafu. Wyróżnia się trzy metody przechodzenia drzew, przy czym ostatnia metoda dotyczy tylko drzew binarnych:
  • pre-order
  • post-order
  • in-order

Problem komiwojażera

 

Cykl Hamiltona to taki cykl w grafie, w którym każdy wierzchołek grafu przechodzony jest tylko jeden raz (oprócz pierwszego wierzchołka). Znalezienie cyklu Hamiltona o minimalnej sumie wag krawędzi jest równoważne rozwiązaniu problemu komiwojażera. Grafy zawierające cykl Hamiltona nazywamy hamiltonowskimi.

Problem komiwojażera (TSP - ang. traveling salesman problem) jest to zagadnienie z teorii grafów, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.
Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość pomiędzy każdą parą miast.
Symetryczny problem komiwojażera polega na tym, że odległość pomiędzy miastami A i B jest zawsze taka sama. W asymetrycznym problemie komiwojażera odległość od miasta A do miasta B może być inna, niż odległość od miasta B do miasta A.

Problem ten jest NP-trudny.

W wersji decyzyjnej problemu, danymi są graf i pewna liczba n, należy odpowiedzieć czy istnieje trasa komiwojażera krótsza od n.
Tak sformułowany problem jest NP-zupełny.