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 projektu: 21.05.2018
Projekt
Zaimplementuj program wczytujący nieskierowany graf z pliku w postaci par wierzchołków połączonych krawędziami. Przykład pliku:
1 2 1 3 2 4 3 4 4 5 4 6 5 6
Zapisz wczytany graf w pamięci programu w postaci macierzy sąsiedztwa oraz macierzy incydencji. Następnie zaimplementuj algorytmy przechodzenia grafu w głąb (DFS) i wszerz (BFS).
Napisz funkcję wczytującą z drugiego pliku pary wierzchołków. Przykład pliku:
1 2 2 7 5 2 5 7
Dla każdej wczytanej pary wierzchołków, sprawdź czy w grafie istnieje między nimi scieżka, przechodząc przez graf metodą DFS oraz BFS, korzystając z obdywu reprezentacji grafu (2 * 2 = 4 sprawdzenia dla każdej pary). Wypisz czas działania funkcji dla poszczególnych reprezentacji, długość znalezionej ścieżki oraz liczbę sprawdzonych krawędzi. Funkcja ma zakończyć się po znalezieniu pierwszej ścieżki lub wypisać 0 jeżeli ścieżka nie istnieje. W przypadku wielu możliwości wybieraj wierzchołek o najmniejszym numerze. Program powinien działać dla grafów o rozmiarze do 10 000 wierzchołków.