Mateusz Gąsiorek 180514

Termin: Środa 16:10

SPRAWOZDANIE

Grafy - Algorytmy Kruskala i Prima

Zaimplementowałem 2 algorytmy

1) Kruskala
2) Prima

Dla dwóch struktur, zależnych od danych wejściowych: macierzy incydencji, oraz listy krawędzi.

Na wstępie opiszę po krótce sortowania:

Algorytm Kruskala wyznacza minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład algorytmu zachłannego.

Algorytm Prima - algorytm zachłanny wyznaczający tzw. minimalne drzewo rozpinające (MDR). Mając do dyspozycji graf nieskierowany i spójny, tzn. taki w którym krawędzie grafu nie mają ustalonego kierunku oraz dla każdych dwóch wierzchołków grafu istnieje droga pomiędzy nimi, algorytm oblicza podzbiór E' zbioru krawędzi E, dla którego graf nadal pozostaje spójny, ale suma kosztów wszystkich krawędzi zbioru E' jest najmniejsza możliwa.

W dalszej części pracy będę przeprowadzał sprawdzanie złożoności czasowej 2 algorytmów dla kilku różnych plików wejsciówych macierzy wag, oraz listy krawędzi.

Swoje wyniki przedstawię w tabeli oraz na wykresach, na koniec wyciągne wnioski wskazując różnice pomiędzy algorytmami:

Swoje doświadczenia przeprowadzam na systemie 32-bitowym Windows 7 pracującym na Intel® Core™2 Duo T5800 2.00GHz. Obliczenia wykonuję za pomocą programu DEV-C++ oraz bibliotek i funkcji związanych z pomiarem czasu w milisekundach.

graf n_100
	LISTY		MACIERZE
		Prim	Kruskal	Prim		Kruskal
		czas	czas	czas	czas	droga
100_150	14	0	15	931	33406
100_600	27	1	15	1149	8923
100_1050	47	5	15	1460	5242
100_1200	57	7	15	1407	4532
100_1500	73	10	15	1865	3903
100_1950	105	19	15	1514	2846
100_2400	114	30	15	1825	2504
100_2850	131	37	15	1538	2078
100_3300	148	49	15	2097	1744
100_3750	165	64	15	1822	1384
100_4200	183	81	15	1164	1213
100_4650	200	100	15	932	1071

graf m_1200
		LISTY		MACIERZE
		Prim	Kruskal	Prim	Kruskal
		czas	czas	czas	czas	droga
1200_50	12	2	5	8	1163
1200_100	30	3	14	24	4532
1200_200	58	9	94	128	20426
1200_300	79	14	245	276	42925
1200_400	124	18	468	652	73882
1200_500	185	23	724	912	110867
1200_600	224	29	958	1249	161605
1200_700	265	38	1197	1567	213265
1200_800	312	51	1437	1885	275847
1200_900	397	69	1676	2203	353511
1200_1000	479	81	1916	2521	427483

WNIOSKI:

• Algorytm Kruskala okazuje się być znacząco lepszy dla listy krawędzi

• Algorytm Prima okazuje się być lepszy dla maceirzy incydencji

• Czas trwania algorytmu kruskala dla listy krawędzi jest mały i nieznacznie się zwiększa, podczas gdy algorytm Prima rośnie w dużym tępie

• Oba algorytmy wyznaczają najkrótsze drzewo rozpinające w poprawny sposób

• Algorytm Kruskala jest opcjonalnym gdy posiadamy dużą ilość wierzchołków

• Oba algorytmy słabo sprawdzają się podczas swojego działania gdy podana jest „duża” macierz. Działania te są wolne, lecz skuteczne

• Gdy dane jest m=1200 algorytmy dla macierzy są znacząco wolniejsze od algorytmów na listach krawędzi.

• Gdy dane jest n=100 oba algorytmy zachowują się w podobny sposób dla macierzy, najgorzej wypada natomiast algorytm Prima dla listy.

DODATKOWE WNIOSKI

• Czasy osiagnięte poprzez algorytm Prima dla listy gdy n=100, są „duze” porównując do pozostałych. Powtórne badania wykazują różnice w czasach w granicach +/- 30 ms. Jest to bład spowodowany obciążeniem chwilowym procesora. Do sprawozdania przyjmuję wartości większe niż średnia.

• W wykresie II dane czasy układają się prawie liniowo. Ponownie wynikęły tutaj znaczące błedy wartości setek podczas powtórnych pomiarów. Wynik zaokrąglony umieszczony w sprawozdaniu.

SPRAWOZDANIE POPRAWIONE

- wersja poprawiona przyśpieszyła działanie Prima

---