Badanie efektywności algorytmów grafowych w zależności od rozmiaru instancji oraz sposobu reprezentacji grafu w pamięci komputera. Należy zaimplementować oraz dokonać pomiaru czasu działania następujących algorytmów grafowych:
[ ] Algorytmy Prima oraz algorytm Kruskala wyznaczający Minimalne Drzewo Rozpinające
[ ] Algorytm Dijkstry oraz algorytm Forda-Bellmana wyznaczający najkrótszą ścieżkę w grafie.
Algorytmy te należy zaimplementować dla obu poniższych reprezentacji grafu w pamięci komputera:
[ ] Reprezentacja macierzowa (macierz adjecencji)
[ ] Reprezentacja listowa (lista następników/poprzedników)
Po zaimplementowaniu każdego z algorytmów dla obu reprezentacji należy dokonać pomiaru czasu działania algorytmów w zależności od rozmiaru grafu oraz jego gęstości (liczba krawędzi w stosunku do liczby wierzchołków) lub struktury (graf równoległy, szeregowy, równoległo-szeregowy, itp.).