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: 23.05.2017
Projekt
Zaimplementuj program wczytujący skierowany graf z pliku w postaci list następników. Przykład pliku:
1: 7 4 2 2: 1 5: 2 3 3: 2 7 6 6: 4 4: 7
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 łuków. 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 przynajmniej 10 000 wierzchołków.