Struktury Danych i
Złożoność Obliczeniowa
Zadanie projektowe nr 2: Badanie efektywności algorytmów grafowych w
zależności od rozmiaru instancji oraz sposobu reprezentacji grafu w
pamięci komputera.
Agnieszka Rybicka  Struktury Danych i Złożoność Obliczeniowa, zadanie projektowe nr 2 1 / 15
1. Wstęp teoretyczny
1.1. Oznaczenia i pojęcia
·ð G = (V, E)  graf o zbiorze wierzchoÅ‚ków V = v & v i krawÄ™dziach E = e & e .
0 n-1 0 m-1
·ð (u, v) õ E  krawÄ™dz
zaczynająca się w wierzchołku u i kończąca wierzchołkiem v.
·ð w(u, v)  waga krawÄ™dzi zaczynajÄ…cej siÄ™ w wierzchoÅ‚ku u i koÅ„czÄ…cej wierzchoÅ‚kiem v.
·ð Maksymalna liczba krawÄ™dzi w grafie skierowanym wynosi 5Ø[Ü " (5Ø[Ü - 1),
5Ø[Ü"(5Ø[Ü-1)
w skierowanym . Graf zawierający maksymalną liczbę krawędzi nazywany jest grafem
2
pełnym.
·ð GÄ™stość grafu  stosunek liczby krawÄ™dzi do maksymalnej liczby krawÄ™dzi
·ð Graf spójny  w przypadku grafu skierowanego to graf, w którym dla każdej pary wierzchoÅ‚ków
istnieje łącząca je ścieżka. Jeśli chodzi o graf skierowany; warunkiem koniecznym spójności jest
spójność grafu podstawowego, czyli bez kierunków na krawędziach. Jeśli tylko ten warunek jest
spełniony, graf jest słabo spójny. Dodatkowo, graf skierowany jest silnie spójny, jeśli między
każdymi dwoma wierzchołkami istnieje ścieżka (przy uwzględnieniu kierunków krawędzi).
·ð Drzewo rozpinajÄ…ce grafu G  drzewo, które zawiera wszystkie wierzchoÅ‚ki grafu G oraz niektóre
jego krawędzie. Jeśli graf ma n wierzchołków, drzewo rozpinające ma n wierzchołków i n-1
krawędzi.
·ð Minimalne drzewo rozpinajÄ…ce grafu G  drzewo rozpinajÄ…ce o najmniejszej sumie wag krawÄ™dzi
ze wszystkich drzew rozpinajÄ…cych grafu G.
1.2. Reprezentacja grafu w pamięci komputera
W niniejszym projekcie używane i porównywane są dwa sposoby reprezentacji grafów; listy
sÄ…siedztwa oraz macierz incydencji.
a) Listy sÄ…siedztwa
Dana jest tablica A, która zawiera n list. Każdy element tablicy odpowiada wierzchołkowi grafu u,
natomiast elementami danej listy są wszystkie wierzchołki sąsiadujące z u. Kolejność sąsiadów na
liście nie ma znaczenia. Aby sprawdzić, czy dana krawędz
(u, v) znajduje się w grafie należy przejrzeć
listę A[u]. Wagi krawędzi pamiętane są w elementach list wraz z wierzchołkiem końcowym i
elementem następnym. Złożoność pamięciowa wynosi O(V2). Przejrzenie wszystkich krawędzi ma
złożoność czasową O(E), natomiast przeglądanie sąsiadów wierzchołka i sprawdzanie istnienia
krawędzi wykonuje się w czasie O(V).
b) Macierz incydencji
Dana jest tablica dwuwymiarowa M. Elementy macierzy m (gdzie i õ 0& n-1,
ij
j õ 0& m-1) przyjmujÄ… wartoÅ›ci:
1 jeśli vi jest początkiem krawędzi ej
5ØZÜ5ØVÜ5ØWÜ = { -1 jeÅ›li vi jest koÅ„cem krawÄ™dzi ej
0 jeśli vi i ej nie są ze sobą związane
W przypadku grafu nieskierowanego, m przyjmuje wartość 1, jeśli v należy do krawędzi e oraz 0,
ij i j
jeżeli nie należy. Złożoność pamięciowa to O(V * E). Operacje przejrzenia wszystkich krawędzi,
sąsiadów danego wierzchołka i sprawdzenie, czy dana krawędz
istnieje wykonujÄ… siÄ™ w czasie O(E).
2 / 15 Agnieszka Rybicka  Struktury Danych i Złożoność Obliczeniowa, zadanie projektowe nr 2
1.3. Zaimplementowane algorytmy
Eksperyment wykonano dla trzech algorytmów grafowych: przeszukiwania w głąb (ang. Depth-first
search), poszukiwania najkrótszych ścieżek oraz wyznaczania minimalnego drzewa rozpinającego
(ang. Minimal Spanning Tree). Czasową złożoność obliczeniową określamy jako ilość czasu niezbędnego do
wykonania algorytmu w zależności od liczby danych wejściowych. Złożoność czasową oznaczamy O(n).
a) Przeszukiwanie grafu w głąb - DFS
Algorytm rozpoczyna się od wierzchołka początkowego v. Odwiedza jego sąsiada u, o ile jeszcze
nie został odwiedzony. Procedura powtarza się do momentu, kiedy dojdzie do wierzchołka v, którego
wszyscy sąsiedzi zostali już odwiedzeni - wtedy wraca do wierzchołka, z którego v został odwiedzony i
przechodzi do jeszcze nieodwiedzonego sąsiada. Złożoność czasowa algorytmu zależy od liczby
wierzchołków i krawędzi, czyli wynosi O(n + m). W projekcie zaimplementowano DFS w wersji
stosowej, to znaczy wykorzystując stos do przechowywania numerów wierzchołków do odwiedzenia.
b) Poszukiwanie najkrótszych ścieżek w grafie  algorytm Dijkstry
Algorytm Dijkstry znajduje w grafie najkrótsze ścieżki pomiędzy wybranym wierzchołkiem a
wszystkimi pozostałymi, wyliczając również koszt przejścia każdej z tych ścieżek, czyli sumę wag
krawędzi na ścieżce. Algorytm ma złożoność czasową O(n2) przy wykorzystaniu wyszukiwania
liniowego podczas szukania wierzchołków o najmniejszym koszcie dojścia. Czas ten może być
zmniejszony dzięki wykorzystaniu kolejki priorytetowej opartej na kopcu binarnym. Wtedy w korzeniu
przechowywany jest wierzchołek o najmniejszej wartości kosztu dojścia. Złożoność czasowa upraszcza
się do O(n * log n)  tyle, ile wynosi czas przywracania własności kopca.
2
c) Wyznaczanie minimalnego drzewa rozpinajÄ…cego  algorytm Prima
Na początku, algorytm dodaje do zbioru A reprezentującego drzewo krawędz
o najmniejszej
wadze, łączącą wierzchołek początkowy v z dowolnym wierzchołkiem. W każdym kolejnym kroku
procedura dodaje do A najlżejszą krawędz
wśród krawędzi łączących wierzchołki już odwiedzone z
nieodwiedzonymi. Jeśli struktura A jest kolejką priorytetową opartą na kopcu binarnym, czasowa
złożoność obliczeniowa operacji wynosi O(m * log n).
2
Agnieszka Rybicka  Struktury Danych i Złożoność Obliczeniowa, zadanie projektowe nr 2 3 / 15
2. Plan eksperymentu
·ð Wagi krawÄ™dzi oraz liczba wierzchoÅ‚ków i krawÄ™dzi sÄ… liczbami caÅ‚kowitymi. W przypadku
losowego generowania grafu, liczba krawędzi jest obliczana na podstawie gęstości podanej
przez użytkownika i zaokrąglona w górę do liczby całkowitej.
·ð Pomiaru czasów wykonania każdego z trzech algorytmów dokonano dla iloÅ›ci wierzchoÅ‚ków
n = {60, 80, 100, 120, 140}. Dla każdej ilości wierzchołków rozważano 4 różne gęstości  25%,
50%, 75% oraz 99%. Przedstawiony w sprawozdaniu czas wykonania algorytmu dla danej
gęstości i ilości wierzchołków jest czasem uśrednionym ze 100 dokonanych pomiarów, a
każdy ze 100 pomiarów odbywał się na nowym, losowo wygenerowanym grafie.
·ð W przypadku DFS i algorytmu Dijkstry, podczas mierzenia czasów losowano wierzchoÅ‚ek, z
którego rozpocznie się algorytm za pomocą funkcji rand().
·ð W implementacji algorytmu Dijkstry krawÄ™dzie grafu wejÅ›ciowego traktowane sÄ… jako
skierowane, natomiast w implementacjach DFS i algorytmu Prima jako nieskierowane. Przy
przeszukiwaniu grafu w głąb nie mają znaczenia wagi krawędzi.
·ð Graf nieskierowany powstaÅ‚y z grafu skierowanego o gÄ™stoÅ›ci g w wiÄ™kszoÅ›ci przypadków
będzie miał większą gęstość niż g.
·ð Dla losowego grafu nie sÄ… generowane krawÄ™dzie wielokrotne ani pÄ™tle, tzn. w grafie nie
znajdą się dwie krawędzie (u, v) oraz nie wystąpi krawędz
(u, u). Przy wczytywaniu z pliku jest
możliwe wprowadzenie takich krawędzi.
·ð Do pomiarów czasu wykorzystano funkcjÄ™
BOOL QueryPerformanceCounter ( __out LARGE_INTEGER *lpPerformanceCount );
4 / 15 Agnieszka Rybicka  Struktury Danych i Złożoność Obliczeniowa, zadanie projektowe nr 2
3. Losowe generowanie grafu
3.1. Losowanie drzewa rozpinajÄ…cego
W celu zapełnienia spójności grafu wyjściowego, czyli połączenia ze sobą wszystkich jego
wierzchołków, generowanie grafu rozpoczyna się budowaniem drzewa rozpinającego. Początkowo, w
zbiorze nieWDrzewie znajdują się wszystkie wierzchołki docelowego grafu. Następnie losowany jest
korzeń drzewa i przenoszony ze zbioru nieWDrzewie do zbioru wDrzewie. W pętli wykonującej się n-1 razy
generowane są kolejne krawędzie drzewa. Wierzchołek początkowy danej krawędzi losowany jest z tablicy
wDrzewie, natomiast wierzchołek końcowy z tablicy nieWDrzewie. Po wylosowaniu wierzchołka
końcowego jest on przenoszony do zbioru wDrzewie. W kolejnej pętli, również wykonującej się n-1 razy,
są zmieniane kierunki losowych krawędzi. Te dwa kroki połączone ze sobą skutecznie zapewniają zmienną
strukturę grafu. Jeśli z gęstości podanej przez użytkownika wynika, że graf ma mieć tylko n-1 krawędzi,
losowanie zakończy się na wygenerowaniu drzewa rozpinającego.
3.2. Dodawanie krawędzi
Jeśli w grafie ma być więcej niż n-1 krawędzi, funkcja przechodzi do losowania kolejnych
wierzchołków, które mają być dołączone do wygenerowanego uprzednio drzewa. Pętla wykonuje się
(m - (n-1)) razy (rozpoczyna się losowaniem krawędzi o numerze n-1). Tworzony jest zbiór wszystkich
wierzchołków T. Losowany jest wierzchołek początkowy wp nowej krawędzi i usuwany z T. Następnie
liczony jest stopień wylosowanego wierzchołka i jeśli jest on równy n-1, losowany jest inny wierzchołek ze
zbioru T, ponieważ przy założeniu braku krawędzi wielokrotnych, z wierzchołka nie wychodzi więcej, niż n-
1 krawędzi. Po ostatecznym wybraniu wp, do zbioru T są przywracane wszystkie wierzchołki i usuwany
wp. Następuje losowanie wierzchołka końcowego wk ze zbioru T i sprawdzenie, czy krawędz
o
wierzchołku początkowym wp i końcowym wk już istnieje w zbiorze krawędzi grafu. Jeśli tak, wybierany
jest nowy wierzchołek wk ze zbioru T. Jeśli oba wierzchołki są już prawidłowo wybrane, zbiór krawędzi jest
rozszerzany o właśnie utworzoną i następuje kolejny obieg pętli. Etap rozszerzania drzewa rozpinającego o
nowe krawędzie zapewnia zmienną strukturę grafu przy jednoczesnym przestrzeganiu założeń o braku
krawędzi wielokrotnych i pętli.
3.3. Nadawanie wag krawędziom
Po zakończeniu poprzednich dwóch etapów generacji krawędzi grafu, m razy wykonuje się pętla
losująca krawędziom wagi z zakresu (1& 9).
3.4. Dodawanie krawędzi odwrotnych
Ponieważ algorytmy DFS oraz Prima wykonuje się na grafie nieskierowanym, generowane są również
krawędzie odwrotne do wcześniej wylosowanych i zapisywane w tablicy KO. Powyższe dwa algorytmy
będą operować na reprezentacjach utworzonych na podstawie zbioru KO. Dla każdej krawędzi (u, v) w
zbiorze K (krawędzie grafu skierowanego) należy sprawdzić, czy w zbiorze KO występuje już krawędz
(v, u)
 jeśli nie, zostaje dodana.
Agnieszka Rybicka  Struktury Danych i Złożoność Obliczeniowa, zadanie projektowe nr 2 5 / 15
4. Wyniki eksperymentu
4.1. DFS
a) Macierz incydencji
Macierz incydencji
Liczba wierzchołków Gęstość [%] Czas [ms]
25 0,967
50 1,418
60
75 1,850
99 2,269
25 1,364
50 2,781
80
75 3,868
99 5,486
25 2,934
50 4,648
100
75 7,427
99 11,349
25 3,966
50 8,095
120
75 11,936
99 14,989
25 7,255
50 12,398
140
75 18,451
99 25,559
Tabela 1  uśrednione czasy wykonania algorytmu DFS dla macierzy incydencji oraz poszczególnych ilości
wierzchołków i gęstości grafu
DFS - macierz incydencji
25,000
20,000
15,000
99%
75%
10,000
50%
25%
5,000
0,000
60 80 100 120 140
Liczba wierzchołków
Wykres 1  czas wykonania algorytmu DFS dla poszczególnych gęstości grafu reprezentowanego przez
macierz incydencji w zależności od liczby wierzchołków
6 / 15 Agnieszka Rybicka  Struktury Danych i Złożoność Obliczeniowa, zadanie projektowe nr 2
Czas [ms]
b) Listy sÄ…siedztwa
Listy sÄ…siedztwa
Liczba wierzchołków Gęstość [%] Czas [ms]
25 0,554
50 0,611
60
75 0,535
99 0,640
25 0,573
50 1,052
80
75 1,151
99 0,956
25 0,942
50 1,076
100
75 1,076
99 1,208
25 1,195
50 1,212
120
75 1,665
99 1,690
25 2,010
50 2,070
140
75 2,605
99 2,153
Tabela 2 - uśrednione czasy wykonania algorytmu DFS dla list sąsiedztwa oraz poszczególnych ilości
wierzchołków i gęstości grafu
DFS - listy sÄ…siedztwa
3,000
2,500
2,000
99%
75%
1,500
50%
25%
1,000
0,500
60 70 80 90 100 110 120 130 140 150
Liczba wierzchołków
Wykres 2 - czas wykonania algorytmu DFS dla poszczególnych gęstości grafu reprezentowanego przez listy
sąsiedztwa w zależności od liczby wierzchołków
Agnieszka Rybicka  Struktury Danych i Złożoność Obliczeniowa, zadanie projektowe nr 2 7 / 15
Czas [ms]
c) Porównanie obu reprezentacji dla stałej gęstości
DFS - gęstość 50%
Macierz incydencji Listy sÄ…siedztwa
12,00
10,00
8,00
6,00
4,00
2,00
0,00
60 80 100 120 140
Liczba wierzchołków
Wykres 3 - czas wykonania algorytmu DFS dla poszczególnych reprezentacji grafu o gęstości 50% w zależności
od liczby wierzchołków
8 / 15 Agnieszka Rybicka  Struktury Danych i Złożoność Obliczeniowa, zadanie projektowe nr 2
Czas [ms]
4.2. Algorytm Dijkstry
a) Macierz incydencji
Macierz incydencji
Liczba wierzchołków Gęstość [%] Czas [ms]
25 0,825
50 1,465
60
75 2,221
99 3,066
25 1,711
50 3,705
80
75 5,648
99 7,882
25 4,857
50 5,963
100
75 8,929
99 14,304
25 7,262
50 10,099
120
75 15,429
99 21,507
25 8,324
50 19,939
140
75 32,484
99 49,955
Tabela 3 - uśrednione czasy wykonania algorytmu Dijkstry dla macierzy incydencji oraz poszczególnych ilości
wierzchołków i gęstości grafu
Dijkstra - macierz incydencji
50,000
45,000
40,000
35,000
30,000
99%
25,000
75%
20,000
50%
15,000
25%
10,000
5,000
0,000
60 80 100 120 140
Liczba wierzchołków
Wykres 4 - czas wykonania algorytmu Dijkstry dla poszczególnych gęstości grafu reprezentowanego przez
macierz incydencji w zależności od liczby wierzchołków
Agnieszka Rybicka  Struktury Danych i Złożoność Obliczeniowa, zadanie projektowe nr 2 9 / 15
Czas [ms]
b) Listy sÄ…siedztwa
Listy sÄ…siedztwa
Liczba wierzchołków Gęstość [%] Czas [ms]
25 0,037
50 0,057
60
75 0,083
99 0,121
25 0,065
50 0,105
80
75 0,144
99 0,195
25 0,093
50 0,226
100
75 0,305
99 0,371
25 0,118
50 0,242
120
75 0,399
99 0,548
25 0,178
50 0,361
140
75 0,573
99 0,780
Tabela 4 - uśrednione czasy wykonania algorytmu Dijkstry dla list sąsiedztwa oraz poszczególnych ilości
wierzchołków i gęstości grafu
Dijkstra - listy sÄ…siedztwa
0,800
0,700
0,600
0,500
99%
0,400
75%
50%
0,300
25%
0,200
0,100
0,000
60 70 80 90 100 110 120 130 140 150
Liczba wierzchołków
Wykres 5 - czas wykonania algorytmu Dijkstry dla poszczególnych gęstości grafu reprezentowanego przez
listy sąsiedztwa w zależności od liczby wierzchołków
10 / 15 Agnieszka Rybicka  Struktury Danych i Złożoność Obliczeniowa, zadanie projektowe nr 2
Czas [ms]
c) Porównanie obu reprezentacji dla stałej gęstości
Dijkstra - gęstość 50%
Macierz incydencji Listy sÄ…siedztwa
20,00
15,00
10,00
5,00
0,00
60 80 100 120 140
Liczba wierzchołków
Wykres 6 - czas wykonania algorytmu Dijkstry dla poszczególnych reprezentacji grafu o gęstości 50% w
zależności od liczby wierzchołków
Agnieszka Rybicka  Struktury Danych i Złożoność Obliczeniowa, zadanie projektowe nr 2 11 / 15
Czas [ms]
4.3. Algorytm Prima
a) Macierz incydencji
Macierz incydencji
Liczba wierzchołków Gęstość [%] Czas [ms]
25 1,181
50 2,243
60
75 2,271
99 2,722
25 2,371
50 3,932
80
75 5,570
99 5,732
25 5,335
50 8,618
100
75 12,039
99 12,499
25 7,616
50 16,509
120
75 18,650
99 19,821
25 12,543
50 23,501
140
75 24,002
99 27,668
Tabela 5 - uśrednione czasy wykonania algorytmu Prima dla macierzy incydencji oraz poszczególnych ilości
wierzchołków i gęstości grafu
Prim - macierz incydencji
30,000
25,000
20,000
99%
15,000
75%
10,000
50%
25%
5,000
0,000
60 80 100 120 140
Liczba wierzchołków
Wykres 7 - czas wykonania algorytmu Prima dla poszczególnych gęstości grafu reprezentowanego przez
macierz incydencji w zależności od liczby wierzchołków
12 / 15 Agnieszka Rybicka  Struktury Danych i Złożoność Obliczeniowa, zadanie projektowe nr 2
Czas [ms]
b) Listy sÄ…siedztwa
Listy sÄ…siedztwa
Liczba wierzchołków Gęstość [%] Czas [ms]
25 0,127
50 0,229
60
75 0,241
99 0,283
25 0,269
50 0,393
80
75 0,474
99 0,552
25 0,404
50 0,550
100
75 0,758
99 0,830
25 0,6326
50 1,079
120
75 1,187
99 1,262
25 0,7929
50 1,430
140
75 1,610
99 1,735
Tabela 6 - uśrednione czasy wykonania algorytmu Prima dla list sąsiedztwa oraz poszczególnych ilości
wierzchołków i gęstości grafu
Prim- listy sÄ…siedztwa
1,800
1,600
1,400
1,200
99%
1,000
75%
0,800
50%
0,600
25%
0,400
0,200
0,000
60 80 100 120 140
Liczba wierzchołków
Wykres 8 - czas wykonania algorytmu Prima dla poszczególnych gęstości grafu reprezentowanego przez listy
sąsiedztwa w zależności od liczby wierzchołków
Agnieszka Rybicka  Struktury Danych i Złożoność Obliczeniowa, zadanie projektowe nr 2 13 / 15
Czas [ms]
c) Porównanie obu reprezentacji dla stałej gęstości
Prim- gęstość 50%
Macierz incydencji Listy sÄ…siedztwa
25,00
20,00
15,00
10,00
5,00
0,00
60 80 100 120 140
Liczba wierzchołków
Wykres 9 - czas wykonania algorytmu Prima dla poszczególnych reprezentacji grafu o gęstości 50% w
zależności od liczby wierzchołków
14 / 15 Agnieszka Rybicka  Struktury Danych i Złożoność Obliczeniowa, zadanie projektowe nr 2
Czas [ms]
5. Wnioski
Rzędy złożoności obliczeniowych zaimplementowanych algorytmów generalnie zgadzają się z danymi
w literaturze pod względem zależności czasu wykonywania operacji od liczby wierzchołków i krawędzi
grafu.
·ð Na wykresach 3, 6 i 9 widać znaczÄ…cÄ… różnicÄ™ miÄ™dzy czasem wykonywania siÄ™ algorytmów w
grafie reprezentowanym za pomocą list sąsiedztwa i za pomocą macierzy incydencji. Różnica
między czasami wzrasta wraz z ilością elementów w grafie. Największa różnica występuje w
przypadku algorytmu Dijkstry, ponieważ wymaga on przejrzenia wszystkich elementów
macierzy, które wykonuje się w dwóch pętlach, natomiast dla listy jest to jedna pętla
przeglądająca sąsiadów wierzchołków.
·ð Wykresy 1 i 2 pokazujÄ…, że wzrost czasu wykonania algorytmu DFS jest zbliżony do liniowego.
W przypadku list sąsiedztwa (wykres 2) linie dla poszczególnych gęstości są skupione blisko
siebie. Może to świadczyć o tym, że w przypadku tej reprezentacji i liczby wierzchołków do
140 różnice w gęstości nie mają dużego znaczenia dla czasu wykonania algorytmu, chociaż z
teoretycznej złożoności czasowej O(E + V) wiadomo, że czas zależy zarówno od liczby
wierzchołków, jak i krawędzi.
·ð Klasa zÅ‚ożonoÅ›ci czasowej algorytmu Dijkstry to O(V * log V). Oznacza to, że zależność czasu
2
wykonania od liczby wierzchołków powinna mieć tendencję logarytmiczną wzmocnioną liczbą
wierzchołków. Na wykresach 4 i 5 jest to zauważalne  linie wykresu są zbliżone do funkcji
logarytmicznej, natomiast wzrost czasu dla każdej gęstości jest gwałtowniejszy od liczby
wierzchołków wynoszącej 120 do 140.
·ð AnalizujÄ…c wykresy 7 i 8 dotyczÄ…ce algorytmu Prima, nie można jednoznacznie stwierdzić,
jakie funkcje one przedstawiają. Linie dla poszczególnych gęstości są skupione dość blisko
siebie, co oznacza niewielkie różnice w czasie wykonywania się algorytmu dla różnej liczby
krawędzi. Wzrost czasu można przybliżyć do wielomianowego, chociaż biorąc pod uwagę
wykresy tylko do liczby wierzchołków równającej się 100, można zauważyć, że wzrost jest
bardzo powolny, przypuszczalnie logarytmiczny.
·ð RozbieżnoÅ›ci pomiÄ™dzy danymi literaturowymi a przedstawionymi wynikami eksperymentu
mogą wynikać z niedokładności pomiaru czasu w systemie Windows, różnej zajętości
procesora podczas wykonywania algorytmów, niedoskonałej implementacji struktur (lista,
tablica, kopiec, kolejka, stos) oraz, przede wszystkim, wpływających na efektywność błędów
w implementacji algorytmów. Ponadto, rzeczywiste kształty wykresów mogą nie być
widoczne przy tak małej ilości danych.
6. Bibliografia
1. Cormen Thomas H., Leiserson Charles E., Rivest Ronald L., Wprowadzenie do Algorytmów, wyd.
IV, Warszawa: Wydawnictwa Naukowo-Techniczne
2. Zakrzewski Marek, Markowe wykłady z Matematyki. Matematyka dyskretna, wyd. I, Wrocław: GiS
3. Algorytm Dijkstry  Wikipedia, wolna encyklopedia
http://pl.wikipedia.org/wiki/Algorytm_Dijkstry
4. Algorytm Prima  Wikipedia, wolna encyklopedia
http://pl.wikipedia.org/wiki/Algorytm_Prima
5. Macierz incydencji  Wikipedia, wolna encyklopedia
http://pl.wikipedia.org/wiki/Macierz_incydencji
Agnieszka Rybicka  Struktury Danych i Złożoność Obliczeniowa, zadanie projektowe nr 2 15 / 15