Zadanie trzecie (Algorytmy grafowe)
Termin zaliczenia zadania + wykres - ; sprawozdanie mailem z wykresami (pdf)- Wygeneruj spójny skierowany graf acykliczny o n wierzchołkach
- współczynnik nasycenia łukami w grafie powinien być równy 50% (czyli 50% z n(n-1)/2)
- najłatwiej jest utworzyć graf acykliczny skierowany poprzez wypełnienie odpowiednią liczbą jedynek górnego trójkąta macierzy sąsiedztwa Graf jest reprezentowany poprzez macierz sąsiedztwa, listę następników oraz tabelę krawędzi. Dla chętnych również macierz grafu. Zaimplementuj dwa algorytmy sortowania topologicznego dla każdej z reprezentacji zgodnie z algorytmem przeszukiwania:
- w głąb - etykietowanie wierzchołków pre- i postorder
- wszerz - wyszukiwanie wierzchołków bez krawędzi wejściowych, usuwanie ich następników, powtarzanie iteracji
- dokonaj pomiaru czasu działania algorytmów dla każdej reprezentacji grafu
- ogólne idee algorytmów, mają być takie same dla różnych reprezentacji grafu, różnice wynikają z innej złożoności wyszukiwania następników w grafie
- nie należy przekształcać każdej reprezentacji np. w liste następników, a nastepnie sortować
- nie należy upraszczać algorytmów ze względu na przygotowanie danych wejściowych (np. macierz sąsiedztwa jest górnotrójkątna i tylko tam sprawdzamy czy są łuki) Pomiary czasu przedstaw na wykresie t=f(n), dla 10 różnych wartości n W sprawozdaniu, oprócz wykresów:
- dla każdej z badanych reprezentacji grafu podaj złożoność: pamięciową, znalezienia pojedynczej krawędzi oraz znalezienia wszystkich następników wierzchołka
- oszacuj złożoność obliczeniową algorytmów sortowania topologicznego (jak się zmienia w zależności od reprezentacji grafu i z czego to wynika)
- które grafy można sortować topologiczne?