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:

Spis treści:              2

Plan doświadczenia              3

Reprezentacja listowa              3

Algorytm Prima              3

Wykres dla grafu o gęstości 10%              3

Wykres dla grafu o gęstości 90%              4

Algorytm Kruskala              4

Wykres dla grafu o gęstości 10%              4

Wykres dla grafu o gęstości 90%              5

Algorytm Dijkstry              6

Wykres dla grafu o gęstości 10%              6

Wykres dla grafu o gęstości 90%              6

Algorytm Forda Bellmana              7

Wykres dla grafu o gęstości 10%              7

Wykres dla grafu o gęstości 90%              8

Reprezentacja macierzowa              8

Algorytm Prima              8

Wykres dla grafu o gęstości 10%              8

Wykres dla grafu o gęstości 90%              9

Algorytm Kruskala              10

Wykres dla grafu o gęstości 10%              10

Wykres dla grafu o gęstości 90%              10

Algorytm Dijkstry              11

Wykres dla grafu o gęstości 10%              11

Wykres dla grafu o gęstości 90%              11

Algorytm Forda Bellmana              12

Wykres dla grafu o gęstości 10%              12

Wykres dla grafu o gęstości 90%              12

Wnioski              13

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%

...