Wprowadzenie
W obecnej części poznamy podstawowe algorytmy służące do wykazania niektórych cech grafów. Algorytmy, czyli skończone ciągi czynności konieczne do wykonania pewnych zadań, czy też rozwiązania niektórych problemów. Zadaniem algorytmu jest zwrócenie żądanego wyniku dla odpowiednich danych wejściowych.
Nie omówimy tutaj implementacji, lecz skupimy się na zrozumieniu samej zasady działania. Większość algorytmów zostało zaimplementowanych w edytorze grafów.
Zanim jednak przejdziemy do algorytmów zdefiniujmy kilka pojęć. Grafem ważonym jest taki graf zawierający krawędzie, którym przypisano pewną liczbę nazywaną wagą krawędzi. Oznaczenie $w(e)$ definiujemy jako wagę krawędzi $e$, przy czym może być nią dowolna wielkość, na przykład: czas dojazdu, odległość, koszt trasy.
Przeszukiwanie grafu wszerz
Przeszukiwanie grafu polaga na odwiedzeniu wszystkich wierzchołków, w celu zebrania informacji o grafie. Jednym z najprostszych procedur tego typu jest przeszukiwanie wszerz. Wiele różnych algorytmów wykorzystuje tę metodę, np: algorytm poszukiwania najkrótszej ścieżki.
Procedura buduje drzewo przeszukiwania wszerz, początkowo zawierające tylko korzeń, którym jest wierzchołek źródłowy. Algorytm najpierw odwiedza wszystkie wierzchołki sąsiadujące z aktualnym wierzchołkiem $v$, zanim przejdzie do następnego wierzchołka. Jeśli wszystkie sąsiednie wierzchołki wierzchołka $v$ zostały odwiedzone, procedura zostaje powtórzona dla sąsiadów $v$ itd.
Przeszukiwanie grafu w głąb
Inną, równie prostą i skuteczną metodą przeszukiwania grafu jest przeszukiwanie w głąb. Algorytm zaczyna działanie w dowolnym wierzchołku, następnie zagłębia się w graf tak daleko, jak jest to tylko możliwe. Jeśli nie istnieje możliwość dalszego przejścia, to wraca do poprzedniego wierzchołka i tam kontunuuje przeszukiwanie itd. W wyniku działania, tworzone zostaje drzewo przeszukiwania w głąb.
Znajdowanie najkrótszej ścieżki
Przypuśćmy, że mamy dany graf ważony $G$. Problem najkrótszej ścieżki polega na znalezieniu drogi, która łączy dwa wybrane wierzchołki i ma najmniejszą całkowitą wagę. Istnieje wiele metod rozwiązania tego zagdnienia. Jednym z najefektywniejszych jest algorytm który opiszemy w tym punkcie.
Oznaczmy dwa wybrane wierzchołki $a$ i $z$, gdzie $a$ jest wierzchołkiem początkowym, a $z$ końcowym. Działanie algorytmu opiera się na tym, aby przeszukiwać graf wszerz i jednocześnie przypisywać każdemu napotkanemu wierzchołkowi $v$ liczbę $l(v)$ okraślającą najkrótszą możliwą odległość od wierzchołka początkowego $a$ do wierzchołka napotkanego $v$.
Znajdowanie cyklu Eulera
W danym grafie eulerowskim należy znaleźć cykl Eulera. Można tego dokonać za pomocą efektywnego algorytmu Fleury'ego, który w czasie pracy korzysta ze znajdowania mostów. Oczywiście graf wejściowy musi być eulerowski, w przeciwnym razie algorytm zawodzi. Cały algorytm wykonuje wszystkie operacje na kopii grafu wejściowego.
Poszukiwanie cyklu zaczynamy w dowolnym wierzchołku o niezerowym stopniu $u$, który będzie startowym. Następnie przechodzimy przez krawędzie w dowolnej kolejności, równocześnie przestrzegając następujacych zasad:
- Usuwaj przechodzone krawędzie i wierzchołki izolowane powstajace w wyniku usuwania tych krawędzi.
- W każdym momencie przechodź przez most tylko wtedy, gdy nie masz innej możliwości.
Problem najkrótszych połaczeń
Zagadnienie najkrótszych połączeń polega na znalezienie w danym grafie ważonym $G$ minimalnego drzewa spinającego $T$, czyli takiego o najmniejszej całkowitej wadze. W tym celu wykorzystamy prosty algorytm zachłanny, działający dla spójnych grafów prostych.
Zaczynamy od utworzenia podgrafu $T$ grafu spójnego $G$. Niech $T$ nie zawiera krawędzi, a jedynie wszystkie wierzchołki grafu $G$, po czym działamy według następujących kroków:
- Wybieramy krawędź $e$ o najmniejszej wadze.
- Następnie sprawdzamy czy $e$ utworzy cykl w $T$. Jeśli nie utworzy, to dodajemy e do zbioru $E(T)$, w przeciwnym razie odrzucamy i szukamy nowej. Kontynuujemy działanie dla pozostałych krawędzi.
Otrzymany w ten sposób podgraf $T$ grafu $G$ jest szukanym rozwiązaniem.
