Konrad Kukulski, 163930 Wrocław, 11.06.2010

Elżbieta Tchorowska, 171067

Struktury danych i złożoność obliczeniowa

Projekt nr 2

Temat: Badanie efektywności algorytmów grafowych w zależności od rozmiaru instancji oraz sposobu reprezentacji grafu w pamięci komputera.

Prowadzący: prof. dr hab. inż. A. Janiak

Spis treści:

Plan doświadczenia

Do przeprowadzenia doświadczenia użyto komputera z procesorem Intel Core Duo 1,86GHz, 1 Gb RAM. Językiem programowania, który posłużył do napisania algorytmów grafowych był C++, pod środowiskiem Dev-C++.

Założenia: grafy posiadają od 100 do 2500 wierzchołków i gęstość od 10% do 90%. .

Reprezentacja listowa

Algorytm Prima

Minimalne drzewo rozpinające

Złożoność obliczeniowa O(v*logv)

Wykres dla grafu o gęstości 10%

Wykres dla grafu o gęstości 90%

Algorytm Kruskala

Minimalne drzewo rozpinające

Złożoność obliczeniowa: O(E*logV)

Wykres dla grafu o gęstości 10%

Wykres dla grafu o gęstości 90%

Algorytm Dijkstry

Najkrótsza ścieżka w grafie

Złożoność obliczeniowa: O(E*logV)

Wykres dla grafu o gęstości 10%

Wykres dla grafu o gęstości 90%

Algorytm Forda Bellmana

Najkrótsza ścieżka w grafie

Złożoność obliczeniowa: O(E*V)

Wykres dla grafu o gęstości 10%

Wykres dla grafu o gęstości 90%

Reprezentacja macierzowa

Algorytm Prima

Wykres dla grafu o gęstości 10%

Wykres dla grafu o gęstości 90%

Algorytm Kruskala

Wykres dla grafu o gęstości 10%

Wykres dla grafu o gęstości 90%

Algorytm Dijkstry

Wykres dla grafu o gęstości 10%

Wykres dla grafu o gęstości 90%

Algorytm Forda Bellmana

Wykres dla grafu o gęstości 10%

Wykres dla grafu o gęstości 90%

Wnioski

Algorytm Prima działa szybciej dla reprezentacji listowej, dla grafów rzadkich.

Algorytm Kruskala działa szybciej dla reprezentacji listowej, dla grafów rzadkich

Algorytm Dijkstry działa szybciej dla grafów rzadkich, przedstawienie nie ma znaczenia.

Algorytm Forda Bellmana działa szybciej dla grafów rzadkich, dla prezentacji listowej.

---