WItam mam takie zadanie
1. W ćwiczeniu rozważa się problem sortowania topologicznego acyklicznego grafu skierowanego - DAG'u.
Zaimplementować procedurę generowania losowego DAG'u o nasyceniu krawędziami 60%. (DAG pełny ma ich n(n-1)/2 - gdzie n liczba wierzchołków).
2. Niech G oznacza acykliczny graf skierowany. Zaimplementować następujący algorytm sortowania topologicznego:
TOPOLOGICAL-SORT(G)
- wykonaj DFS(G) w celu obliczenia czasów przetworzenia dla wszystkich wierzchołków G,
- wstaw każdy wierzchołek v na początek listy, kiedy tylko zostanie przetworzony (pokolorowany na czarno),
- return lista wierzchołków.
gdzie DFS jest algorytmem przeszukiwania grafu w głąb. Implementacja powinna być oparta na liście incydencji oraz na macierzy sąsiedztwa.
3. Przeprowadzić pomiary czasu działania Algorytmu w zależności od liczby n wierzchołków w grafie. Wyniki przedstawić na wykresie t = f(n) dla dwóch reprezentacji grafu: macierz sąsiedztwa i lista incydencji.
5. Sformułować wnioski odnośnie doboru odpowiedniej reprezentacji grafu dla problemu sortowania topologicznego. Podać zalety i wady wybranych reprezentacji w odniesieniu do badanego problemów.
Podać i uzasadnić złożoność obliczeniową badanych algorytmów.
Jestem laikiem w programowaniu a musze to zaliczyc.... wiec proszę o pomoc...jestem gotowy ponieść koszty $
Proszę o szybką odpowiedź