Zagadnienia

• Definicja grafu skierowanego i nieskierowanego
• Reprezentacje grafu, ich złożoność pamięciowa i złożoność pozyskiwania informacji o grafie z poszczególnych struktur danych
• Algorytmy przeszukiwania grafu “w głąb” (Depth First Search = DFS) oraz “wszerz” (Breadth First Search = BFS)
• Algorytm znajdowania cyklu Eulera w grafie, warunki istnienia cyklu Eulera w grafie skierowanym i nieskierowanym, złożoność obliczeniowa procedury poszukiwania cyklu Eulera
• Metoda poszukiwania minimalnego drzewa rozpinającego w grafie oraz jej złożoność obliczeniowa
• Algorytm sortowania topologicznego

Termin oddawania programów i wyników eksperymentów (+ wykresy): 17.5.2016
Termin dostarczenia sprawozdania (mailem pdf): 24.5.2016

Projekt

Zaimplementuj algorytmy przechodzenia grafu w głąb (DFS) i wszerz (BFS) dla następujących reprezentacji grafu skierowanego:

• lista następników,
• macierz sąsiedztwa

Wygeneruj grafy skierowane o n wierzchołkach i współczynniku nasycenia krawędziami równym 50% (oznacza to, że liczba krawędzi grafu wynosi 50% z n(n-1)/2), nie będące multigrafami, dla różnych wartości n

Wykonaj wykres dla każdej reprezentacji grafu, zależności czasu obliczeń t od liczby n wierzchołków w grafie. Na każdym wykresie przedstaw 2 krzywe – po jednej krzywej dla każdej metody przechodzenia grafu.

Wykonaj 2 wykresy (jeden wykres dla każdej metody przechodzenia grafu) t=f(n) zależności czasu obliczeń t od liczby n wierzchołków w grafie. Na każdym wykresie przedstaw po jednej krzywej dla każdej reprezentacji grafu.

Opisz zalety i wady każdej reprezentacji grafu z punktu widzenia ich zastosowania w algorytmach DFS i BFS.