MOKIP 15 X 2012 (gr. podstawowa)

Algorytmy grafowe DFS, BFS

1. Przypomnienie z poprzednich zajęć:

• czym jest graf G = (V, E)
• własności grafu (skierowany, nieskierowany, ważony, nieważony, spójny, …)

2. Sposoby przechowywania grafu w pamięci:
a) STL'owy vector

• dobry nawet dla dużych grafów
• w miarę szybkie sprawdzanie znajomych wierzchołka 'u'

b) macierz n*n:

• 1 jeśli jest krawędź, 0 w przeciwnym wypadku
• bardzo szybki, sprawdzanie czy istnieje krawędź w czasie O(1)
• dobry dla grafów < 100 000, potem zajmuje za dużo miejsca

3. DFS (Deep First Search - przeszukiwanie w głąb) i zastosowania:

• pseudokod rekurencyjny
• tablica visited [n], kolorowanie grafu (umożliwia wykrywanie cykli)
• umożliwia obliczenie tablicy: pre/in/post-order i innych…

4. BFS (Breadth First Search - przeszukiwanie wszerz) i zastosowania:

• odnalezienie najkrótszej ścieżki między więrzchołkiem startowym a wszystkimi pozostałymi (tylko dla jednostkowych/takich samych wag krawędzi)
• sprawdza czy graf jest dwudzielny (czy istnieje cykl Hamiltona)

5. Zadanie a w razie problemów rozwiązanie (już wkrótce :)