Uniwersytet im. Adama Mickiewicza w Poznaniu
Wydział Fizyki, kierunek informatyka stosowana
Algorytmy i struktury danych
Notatki do wykładów dr in\
. Pawła Prałata
Opracowane przez: Piotr Knychała
[e-mail]
http://www.czbobry.int.pl
Kalisz 2004-2005
Ostatnia aktualizacja VIII 2005
Za błędy w treści materiałów nie odpowiadam.
Algorytmy i struktury danych
Spis treści:
Efektywność........................................................................................................................................................... 5
Notacja  wielkie O ........................................................................................................................................... 5
Notacje: &! i Åš .................................................................................................................................................... 6
Listy........................................................................................................................................................................ 6
Dokładanie elementu do listy ............................................................................................................................. 7
Wyszukiwanie elementu w liście......................................................................................................................... 7
Usuwanie elementu z listy .................................................................................................................................. 7
Listy cykliczne (rozwiÄ…zanie problemu Josephusa)............................................................................................ 8
Stos (LIFO  Last In First Out) ........................................................................................................................... 9
Implementacja stosu z wykorzystaniem tablicy .................................................................................................. 9
Implementacja stosu z wykorzystaniem listy jednokierunkowej ....................................................................... 10
Kolejka (FIFO  First In First Out) .................................................................................................................. 10
Implementacja kolejki z wykorzystaniem tablicy.............................................................................................. 11
Implementacja kolejki z wykorzystaniem listy jednokierunkowej..................................................................... 12
Kolejka priorytetowa (wykorzystanie kopca) ................................................................................................... 12
Kopiec................................................................................................................................................................... 13
Naprawianie kopca .......................................................................................................................................... 14
Tworzenie kopca............................................................................................................................................... 15
Sortowanie danych.............................................................................................................................................. 16
Sortowanie przez wstawianie (ang. insertion sort)........................................................................................... 16
Sortowanie przez wybór (ang. selection sort) .................................................................................................. 17
Sortowanie bÄ…belkowe - wersja standardowa i ulepszona (ang. bubble exchange sort).................................. 17
Sortowanie Shella (ang. shellsort) ................................................................................................................... 18
Sortowanie przez kopcowanie (ang. heapsort)................................................................................................. 19
Sortowanie szybkie  wersja standardowa oraz z losowym elementem dzielÄ…cym (ang. quicksort) ................ 20
Sortowanie przez scalanie (ang. mergesort) .................................................................................................... 21
Sortowanie przez zliczanie (ang. counting sort)............................................................................................... 22
Sortowanie stabilne .......................................................................................................................................... 23
Sortowanie pozycyjne (ang. radix sort)............................................................................................................ 23
Sortowanie kubełkowe (ang. bucket sort)......................................................................................................... 24
Algorytmy rekurencyjne .................................................................................................................................... 25
Proste algorytmy rekurencyjne......................................................................................................................... 26
Silnia............................................................................................................................................................ 26
NWD  największy wspólny dzielnik (algorytm Euklidesa)....................................................................... 26
Wypisywanie wyrazu od końca ................................................................................................................... 26
Algorytmy zachłanne (ang. greek algorithm) ................................................................................................... 27
Problem kasjera ........................................................................................................................................... 27
Szukanie minimum funkcji.......................................................................................................................... 27
2
Algorytmy i struktury danych
Strategia  dziel i rzÄ…dz
 ................................................................................................................................... 28
Wyznaczanie wartości maksymalnej ........................................................................................................... 28
Linijka ......................................................................................................................................................... 28
Wie\
a Hanoi ................................................................................................................................................ 28
CiÄ…g liczb Fibonacciego .............................................................................................................................. 29
Programowanie dynamiczne ............................................................................................................................ 29
CiÄ…g liczb Fibonacciego .............................................................................................................................. 29
Liczba kombinacji  trójkąt Pascala ............................................................................................................ 29
Problem pakowania plecaka (ang. knapsack problem)................................................................................ 30
Rozkład na czynniki pierwsze liczb naturalnych (0-1000).......................................................................... 32
Metoda powrotów   prób i błędów (ang. backtracking).............................................................................. 32
Problem skoczka szachowego ..................................................................................................................... 32
Problem ośmiu hetmanów ........................................................................................................................... 33
CoÅ› na deser..................................................................................................................................................... 34
Krzywa Kocha (płatek śniegu) .................................................................................................................... 34
Trójkąt i dywan Sierpińskiego..................................................................................................................... 34
Krzywa Hilberta .......................................................................................................................................... 34
Zliczanie białych obszarów i liczby białych pól w ka\
dym obszarze ......................................................... 35
Drzewo binarne  implementacja podstawowych operacji ............................................................................. 36
Dodawanie elementu ........................................................................................................................................ 36
Wyszukiwanie elementu, element minimalny i maksymalny ............................................................................. 37
Usuwanie elementu (3 przypadki) .................................................................................................................... 38
Przechodzenie drzewa w głąb i wszerz............................................................................................................. 40
Równowa\
enie drzewa ..................................................................................................................................... 41
Metoda z wykorzystaniem pomocniczej tablicy.......................................................................................... 41
Algorytm DSW............................................................................................................................................ 42
Tablice haszujÄ…ce ................................................................................................................................................ 48
Funkcje haszujÄ…ce  metody ich wyznaczania.................................................................................................. 49
Rozwiązywanie kolizji metodą łańcuchową...................................................................................................... 50
Adresowanie otwarte........................................................................................................................................ 50
Teoria grafów ...................................................................................................................................................... 53
Podstawowe definicje....................................................................................................................................... 53
Reprezentacja grafów w komputerze................................................................................................................ 58
Przechodzenie grafu w głąb, wyznaczanie spójnych składowych..................................................................... 59
Przechodzenie grafu wszerz ............................................................................................................................. 60
Sortowanie topologiczne .................................................................................................................................. 60
Wyznaczanie silnych spójnych składowych w grafie skierowanym .................................................................. 61
TrochÄ™ o Å‚Ä…czeniu w zbiory............................................................................................................................... 64
Minimalne drzewo rozpinajÄ…ce ........................................................................................................................ 66
Algorytm Kruskala ...................................................................................................................................... 67
Algorytm Prima ........................................................................................................................................... 68
Najkrótsze ście\
ki z jednym z
ródłem ................................................................................................................ 69
Algorytm Dijkstry ....................................................................................................................................... 69
Algorytm Bellmana  Forda ........................................................................................................................ 73
Maksymalny przepływ ...................................................................................................................................... 74
Maksymalne skojarzenia w grafie dwudzielnym .............................................................................................. 77
3
Algorytmy i struktury danych
Obliczanie wielomianu chromatycznego.......................................................................................................... 78
Dodatek: Algorytmy wyszukiwania wyrazu wzorcowego w tekście ................................................... 81
Metoda  naiwna ............................................................................................................................................ 81
Metoda Rabina-Karpa...................................................................................................................................... 81
Metoda Knuta-Morrisa-Pratta ......................................................................................................................... 82
Zakończenie....................................................................................................................................................... 83
4
Algorytmy i struktury danych
Efektywność
Początkowi programiści pisząc program cieszą się, gdy się kompiluje, a gdy działa
poprawnie to ju\
w ogóle są w raju. Jednak im bardziej skomplikowane programy piszemy,
nale\
y coraz bardziej zwracać uwagę na szybkość ich działania. Wa\
ne jest to szczególnie
wtedy, gdy program ma operować na du\
ej liczbie danych. Problemy mo\
na rozwiązać na
wiele sposobów, chodzi o to, aby wybrać najbardziej efektywny (czyli taki, który najszybciej
doprowadzi nas do celu). Właśnie efektywność algorytmów porównuje się obliczając tzw.
zło\
oność obliczeniową. Określa ona m.in. ilość czasu i pamięci, jaka jest potrzebna do
rozwiÄ…zania problemu.
Szybkość wykonywania danego programu zale\
y od wielu czynników, nie tylko od
zło\
oności algorytmu. Na ten czynnik ma tak\
e wpływ rodzaj sprzętu, na którym
uruchomiony jest program. Znaczenie ma tak\
e język, w jakim program został napisany.
Do opisu zło\
oności algorytmu nie stosuje się jednostek czasu, takich jak sekunda czy
mikrosekunda, lecz opisuje siÄ™ jÄ… podajÄ…c zale\
ność, z jaką zmienia się czas w stosunku do
wzrostu liczby danych. Przykładowo: je\
eli zwiększenie danych do przetworzenia wzrasta
3-krotnie, to czas potrzebny na tÄ… operacjÄ™ te\
wzrośnie 3-krotnie. Mo\
na tÄ… zale\
ność
przedstawiać w postaci wzoru t(n). np. t(n)=n (zale\
ność liniowa). Funkcje przedstawiające
takÄ… zale\
ność są w rzeczywistości bardziej skomplikowane i bardzo często pomija się w
nich składniki nie mające znaczącego wpływu na jej wartość. Wtedy zło\
oność obliczona w
takim wzorze jest przybli\
ona, ale dla bardzo du\
ego n jest i tak dość dokładna. Taki sposób
obliczania efektywności algorytmu określa się mianem zło\
oności asymptotycznej.
Szybkość wzrostu poszczególnych składników przykładowej funkcji wyznaczającej
zło\
oność asymptotyczną podano w poni\
szej tabeli.
2
f (n ) = n + 100 n + log n + 1000
10
n f(n) n2 100n log10n 1000
1 1101 1 100 0 1000
10 2101 100 1000 1 1000
100 21002 10 000 10 000 2 1000
1000 1101003 1 000 000 100 000 3 1000
10 000 101001004 100 000 000 1 000 000 4 1000
100 000 10010001005 10 000 000 000 10 000 000 5 1000
Tabela 1: Efektywność - przykład (z
ródło: A. Drozdek - "Struktury danych w języku C").
AnalizujÄ…c tabele widzimy, \
e dla małych wartości n największy wkład do wyniku funkcji
wnosi ostatni składnik (1000). Przy wzroście n do wartości 10 zarówno składnik 100n, jak i
1000 dają taki sam wkład. Dla n równego 100 największy wkład wnosi część n2 oraz 100n.
Dla wartości n powy\
ej 100 widać wyraz
nie, \
e kwadratowa szybkość wzrostu składnik n2
powoduje, \
e wnosi on największy wkład i wartość funkcji zale\
y głównie od niego. Zatem
dla dostatecznie du\
ych n pozostałe składniki mo\
na zaniedbać.
Notacja  wielkie O
Jest to jedna z powszechniej stosowanych notacji opisująca zło\
oność asymptotyczną.
Funkcja f(n) jest O(g(n)), jeśli istnieją liczby dodatnie c i N takie, \
e f(n) d" cg(n) dla
wszystkich ne"N.
Co znaczy tyle, \
e jeśli mamy daną funkcję:
f (n) = 2n2 + 3n +1
to funkcja cg(n) dla wszystkich ne"N opisuje przybli\
ona wartość zło\
oności asymptotycznej
funkcji f(n). Stałe c i N wyznacza się z równania:
5
Algorytmy i struktury danych
2n2 + 3n +1 = cn2
Jak widać nie jest wcale łatwo wyznaczyć jednoznaczną wartość c, poniewa\
zale\
y ona od
jakich ne"N będzie spełniona zale\
ność f(n)d"cg(n). Dodatkowo mo\
na przyjąć za g(n) wiele
innych funkcji, m.in. n3, n4, itd. Dlatego notacjÄ™ "wielkie O" stosuje siÄ™ tylko pomijajÄ…c
najmniej znaczące składniki. Dla naszego przykładu wygląda to następująco: f(n) =
2n2+O(n), albo f(n) = O(n2) albo f(n) = O(n3).
Notacje: &! i Åš
Poprzednia notacja ograniczała funkcję od góry. Notacja  omega ogranicza ją od dołu.
Funkcja f(n) jest &!(g(n)), jeśli istnieją liczby dodatnie c i N takie, \
e f(n) >= cg(n) dla
wszystkich ne"N.
Podobnie jak w poprzedniej notacji mamy do czynienia z takÄ… samÄ… zasadÄ…, lecz
wyznaczającą funkcję ograniczającą f(n) od dołu. Pojawiają się tu te same problemy istnienia
nieskończenie wielu takich funkcji oraz zale\
ności stałej c od N.
A
Ä…czÄ…c te dwie notacje uzyskujemy notacjÄ™  teta .
Funkcja f(n) jest Ś(g(n)), jeśli istnieją liczby dodanie c1,c1 i N takie, \
e c1g(n)d" f(n) d" c2g(n)
dla wszystkich ne"N.
OpierajÄ…c siÄ™ na notacji "wielkiego O" nie zawsze uzyskujÄ™ siÄ™ dobre rezultaty.
Zale\
ność zachodzi dla wszystkich n z wyjątkiem pewniej skończonej liczby n, które jej nie
spełniają. Mo\
na ograniczać tą ilość n zwiększając c, ale wtedy obliczona zło\
oność staje się
mniej dokładna.
Algorytmy mo\
na podzielić na klasy, które określają szybkość wzrost t w zale\
ności od
n.
Nazwa klasy ZÅ‚o\
oność klasy
stały- czas nie zale\
y od n (jest const) Åš(1)
logarytmiczny Åš(ln n)
liniowy Åš(n)
kwadratowy Åš(n2)
sześcienny Ś(n3)
wykładniczy Ś(2n)
Tabela 2: Klasy zło\
oności algorytmów.
Listy
W przypadku tablicy mieliśmy sytuację, w której kolejne elementy tablicy były
przechowywane w pamięci jeden po drugim. Dynamiczne przydzielanie pamięci umo\
liwia
nam tworzenia dynamicznych wiÄ…zanych struktur danych. CharakteryzujÄ… siÄ™ one tym, \
e
ka\
dy element oprócz swoich danych zawiera tak\
e informacjÄ™, gdzie znajduje siÄ™ kolejny
element w strukturze. Przykładem takiej struktury danych są listy.
Listy to struktura danych słu\
ąca do przechowywania z góry nieznanej ilości
informacji tego samego typu. Skład się ona z węzłów, które zawierają dane przechowywane
w liście oraz wskaz
nik do kolejnego elementu. ListÄ™ rozpoczyna wskaz
nik do poczÄ…tku, a
ostatni element wskazuje na NULL.
6
Algorytmy i struktury danych
Nazwa Opis
Ka\
dy element zawiera wskaz
nik do następnego elementu. Listę
jednokierunkowe
mo\
emy przechodzić tylko w jednym kierunku.
Ka\
dy element zawiera wskaz
nik do następnego i poprzedniego
dwukierunkowe elementu. Dzięki temu listę mo\
emy przechodzić od początku do końca i
odwrotnie.
Na poczÄ…tku listy znajduje siÄ™ dodatkowy element (wartownik) nie
z wartownikiem
przechowujÄ…cy konkretnych danych, ale usprawniajÄ…cy usuwanie.
bez wartownika Lista nie posiadajÄ…ca dodatkowego elementu na poczÄ…tku (wartownika).
posortowane Elementy listy są uło\
one w sposób uporządkowany.
nie posortowane Przypadkowe rozmieszczenie elementów na liście.
Tabela 3: Rodzaje list.
Dokładanie elementu do listy
Dokładanie elementów na końcu listy nie jest dobrym rozwiązaniem poniewa\
aby to
zrobić nale\
ało by przejść całą listę, co spowalnia proces. Dlatego najlepiej dokładać element
na poczÄ…tku listy. WyjÄ…tkiem jest sytuacja, gdy mamy do czynienia z listÄ… posortowanÄ….
Wtedy nale\
y poszukać miejsca, w którym nale\
y wstawić element. Jeśli nasza lista jest
posortowana rosnąco, to przechodzimy ją od początku dopóty, dopóki wstawiany element
jest większy od aktualnie odwiedzanego na liście. Jeśli warunek ten nie zostanie spełniony to
nale\
y wstawić nowy element przed aktualnie odwiedzonym na liście.
pocz
NULL
5 1 9 4
2
czerwone Å‚Ä…cze usuwamy (przed);
niebieskie dokładamy (po);
Wyszukiwanie elementu w liście
Mo\
na tu rozwa\
ać listy nie posortowane i posortowane. W pierwszym przypadku
musimy niestety przejść całą listę od początku do końca poniewa\
szukany element mo\
e
znajdować się w dowolnym miejscu listy. Jeśli natomiast nasza lista jest posortowana to
poszukujemy elementu tak długo, a\
go nie znajdziemy lub aktualnie odwiedzany element
listy jest większy od szukanego (przypadek dla list posortowanych rosnąco, dla przeciwnej
sytuacji element musi być mniejszy).
Usuwanie elementu z listy
Problem ten mo\
na rozwa\
ać dla kilku sytuacji. Na początek zajmijmy się listą
nieposortowanÄ… bez wartownika. Zanim rozpoczniemy poszukiwanie elementu do
usunięcia sprawdzamy czy lista nie jest pusta. Gdyby się tak zdarzyło, to nie robimy nic.
Mo\
e się zdarzyć równie\
sytuacja, w której element do usunięcia znajduje się na początku
listy. Wtedy wystarczy ustawić wskaz
nik początku na drugi element listy i usunąć pierwszy.
7
Algorytmy i struktury danych
pocz
NULL
5 1 9 4
czerwone kreski wywalamy (przed);
niebieską dokładamy (po);
Ostatni przypadek dotyczy sytuacji, w której usuwany element znajduje się na n-tym
miejscu na liście. Nale\
y najpierw go odnalez
ć, a następnie usunąć. Nale\
y pamiętać o
odpowiednim ustawieniu wskaz
nika elementu poprzedzajÄ…cego usuwany element.
pocz
NULL
5 1 9 4
czerwone kreski wywalamy (przed);
niebieską dokładamy (po);
Jeśli nasza lista posiada wartownika, to operacja usuwania sprowadza się do jednego
przypadku. Jest to ostatni opcja spośród opisanych powy\
ej. Zawsze będziemy usuwać
element z n-tej pozycji na liście. Skróci do ilość operacji niezbędną do usunięcia elementu
(nie trzeba rozwa\
ać przypadków).
Warto jeszcze zwrócić uwagę na listy posortowane. Powróćmy do przypadku listy
posortowanej rosnąco. Jeśli poszukujemy elementu do usunięcia i w pewnym momencie
(przechodzÄ…c listÄ™) zorientujemy siÄ™, \
e aktualnie odwiedzany element jest większy od
poszukiwanego, to oznacza to, \
e nie ma na liście elementu, który chcemy usunąć.
Kończymy dalsze przechodzenie listy.
Listy cykliczne (rozwiÄ…zanie problemu Josephusa)
Jest to specyficzny rodzaj listy. Charakterystyczne jest to, \
e ostatni element listy
wskazuje na pierwszy element na liście, co sprawia, \
e lista tworzy strukturÄ™ cyklicznÄ….
Znany problem, który mo\
na rozwiązać przy pomocy listy cyklicznej to problem Josephusa.
Mamy n osób, które będą się zabijać nawzajem :&. Umierać będzie co k-ta osoba. Nale\
y tak
dobrać k, aby konkretna osoba prze\
yła (jeśli osoba dobierająca k, zrobi to poprawnie  to
prze\
yje :&). Umieszczając numery osób na liście cyklicznej, mo\
emy uśmiercać co k-ty
element dopóty, dopóki nie zostanie nam jeden element na liście. W ten sposób dowiemy się
kto został szczęśliwcem.
5
4
0
9
7
2
8
Algorytmy i struktury danych
Stos (LIFO  Last In First Out)
Stos to struktura danych, w której ostatni element wło\
ony na stos jest zdejmowany
jako pierwszy. Mo\
na to porównać do stosu ksią\
ek. Je\
eli na stole le\
y stos poło\
onych
jedna na drugiej ksiÄ…\
ek to zawsze najlepiej rozpocząć zdejmowanie tych ksią\
ek od góry
(wyciÄ…ganie ksiÄ…\
ki spod spodu nie jest mo\
liwe).
Dokładamy Zdejmujemy
elementy na elementy ze
stos stos
3
2 2 2
1 1 1 1 1
Omówimy teraz dwie metody realizacji stosu. Pierwsza, gdy mamy ograniczony
rozmiar stosu, wtedy tworzymy tablicÄ™ i umieszczamy elementy stosu w tablicy. Drugi, gdy
rozmiar stosu jest nieograniczony (właściwie to ogranicza go ilość pamięci). Wtedy
tworzymy wskaz
nik, który będzie pokazywał na pierwszy element stosu, a ka\
dy kolejny
element stosu przechowuje wskaz
nik do kolejnego (realizacja tak jak w przypadku listy). W
pierwszym przypadku elementy odkładamy do kolejnych komórek tablicy i zdejmujemy od
końca tablicy. W drugim, kolejne elementy dokładamy na początku kolejki i zdejmujemy
tak\
e od poczÄ…tku kolejki.
Implementacja stosu z wykorzystaniem tablicy
PierwszÄ… metodÄ™ stosujemy, gdy znamy maksymalny rozmiar stosu. Wtedy
tworzymy tablice i umieszczamy elementy stosu w tablicy. Metoda ta z góry ogranicz nam
ilość elementów jaką maksymalnie mo\
na wrzucić na stos. Elementy odkładamy w
kolejnych komórkach tablicy i zdejmujemy w odwrotnej kolejności  wstawiony jako ostatni,
będzie zdjęty jako pierwszy.
Pseudokod:
class stos
{ int empty(){
int rozmiar, ilosc; //sprawdzenie czy stos jest pusty
int * tablica; return (ilosc == 0);}
public: int put(int s) {
//jeśłi stos nie jest pełen
// konstruktor if (ilosc == rozmiar)
stos(int rozmiar){ return 0;
//ustalenie wartości początkowych //dodanie elementu
this->rozmiar = rozmiar; tablica[ilosc++] = s;
this->ilosc = 0; return 1; }
//przydzielenie pamięci
tablica = new int [rozmiar];} int get(){
//jeśli stos nie jest pusty
// destruktor if (empty()) return 0;
~stos(){ //zdjęcie elementu
//zwolnienie pamięci return tablica[--ilosc]; }
delete [] tablica; } };
9
Algorytmy i struktury danych
Implementacja stosu z wykorzystaniem listy jednokierunkowej
Drugą metodę stosujemy, gdy nie da się przewidzieć ile elementów znajdzie się na
stosie (ilość elementów jest oczywiście ograniczona przez ilość dostępnej pamięci). Dla
takiego przypadku najlepiej jest wykorzystać listę jednokierunkową, nieuporządkowaną.
Elementy będziemy dokładać na początku listy i zdejmować równie\
od poczÄ…tku listy.
Pseudokod:
class stos tmp=pocz;
{ //przesuń początek początek 1
//pojedynczy element stosu pocz=pocz->nast;
class wezel { //usuń element
public: delete tmp;}}
int w;
wezel *nast; }; void stos::dodaj(int s){
wezel *pocz; //stwórz nowy element
public: wezel *nowy=new wezel;
nowy->w=s;
//konstruktor //ustaw wskaz
niki
stos(){ nowy->nast=pocz;
pocz=NULL; pocz=nowy;}
}
//deklaracje int stos::usun(){
~stos(); //jeśli nie pusty
void dodaj(int); if (!pocz) return 0;
int usun(); int liczba=pocz->w;
}; //ustaw wskaz
niki
//destruktor wezel *wsk=pocz;
stos::~stos(){ pocz=pocz->nast;
wezel *tmp; //zwolnij pamięć
//jeśli nie pusty delete wsk;
while (pocz){ return liczba;}
Kolejka (FIFO  First In First Out)
Kolejka to struktura danych, w której element, który został wstawiony do kolejki jako
pierwszy, jako pierwszy z niej jest wyciągnięty. Tę strukturę mo\
na porównać do kolejki w
sklepie. Osoba, która jako pierwsza przyjdzie do sklepu, jako pierwsza zostanie w nim
obsłu\
ona i pierwsza wyjdzie ze sklepu (pomijamy tu sytuacje ekstremalne :)). Wepchnięcie
się do kolejki nie jest najlepszym pomysłem, poniewa\
mo\
e siÄ™ z
le dla nas skończyć.
1
1. Wstawiamy
element do
kolejki
1 2
2.
1 2 3
3.
WyciÄ…gamy
2 3
4.
element z
kolejki
3
5.
Podobnie jak w przypadku stosu, mo\
liwe sÄ… dwa sposoby realizacji kolejki. Pierwszy
w tablicy (co ogranicza rozmiar kolejki). Drugi, bazujÄ…c na strukturze zwanej listÄ….
Tworzymy wskaz
nik do poczÄ…tku kolejki, a ka\
dy kolejny składnik kolejny przechowuje
wskaz
nik do kolejnego elementu kolejki. Dodatkowo tworzymy wskaz
nik, który
przechowuje adres końca kolejki. Elementy do kolejki wstawiamy od początku struktury, a
zdejmujemy od końca lub na odwrót.
10
Algorytmy i struktury danych
Implementacja kolejki z wykorzystaniem tablicy
Pierwsza metoda wykorzystuje tablice. Jak wspomniano ju\
przy okazji stosu,
rozwiązanie takie z góry ogranicza maksymalną ilość elementów w kolejce. Jednak pojawia
się tu jeszcze jeden problem. Otó\
dane dodawane do kolejki umiejscawiamy w kolejnych
komórkach tablicy a zdejmujemy je z początku tablicy. Mo\
e się zdarzyć sytuacja, w której
dojdziemy do końca tablicy i nie będzie mo\
liwe wstawienie kolejnych elementów. Jednak
jeśli z początku tablicy zostały ju\
zdjęte jakieś elementy, to mo\
na rozpocząć uzupełnianie
kolejki od początku tablicy. Wyobrazić sobie nale\
y, \
e nasza tablica ma kształt pierścienia.
DodajÄ…c element do kolejki nale\
y pamiętać, \
e wyznaczajÄ…c indeks kolejnego wolnego
miejsca w tablicy nale\
y zabezpieczyć się przed wyjściem poza obszar pamięci przypisany
do tablicy. Robimy to dzielÄ…c indeks kolejnego wolnego elementu modulo przez rozmiar
tablicy.
0 1
1
7
5 2
2 3
6
3
4 7
5
4
Pseudokod:
class kolejka tab[kon]=s;
{ ile++;
int *tab; //przesuń indeks
int roz; kon=(kon+1)%roz;
int ile,pocz,kon; return 1;}
public: //jeśli brak miejsca
if (kon==pocz) return 0;
//konstruktor //niepusta, wolna kolejka
kolejka(int roz){ tab[kon]=s;
this->roz=roz; kon=(kon+1)%roz;
ile=pocz=kon=0; ile++;
tab= new int[roz];} return 1;
//destruktro }
~kolejka(){ //usuwanie elementu
delete [] tab;} int kolejka::pop(){
//dekslaracje //jeśli pusta
int push(int s); if(!ile) return 0;
int pop(); //zdjęcie elementu
}; int liczba=tab[pocz];
//dodawanie elementu //ustalenie indeksu
int kolejka::push(int s){ pocz=(pocz+1)%roz;
//jeśli kolejka pusta ile--;
if (!ile){ return liczba;
//dodaj element }
11
Algorytmy i struktury danych
Implementacja kolejki z wykorzystaniem listy jednokierunkowej
Druga metoda polega na wykorzystaniu listy jednokierunkowej, nieposortowanej.
ListÄ™ takÄ… nale\
y minimalnie zmodyfikować dokładając dodatkowy wskaz
nik wskazujÄ…cy
zawsze na ostatni element na liści. Element do kolejki dodajemy na końcu kolejki, a
zdejmujemy z poczÄ…tku.
Dodawanie elementu do kolejki:
pocz
NULL
5 1 9 4
2
kon
Usuwanie elementu z kolejki:
pocz
NULL
5 1 9 4
kon
czerwone kreski wywalamy (przed);
niebieską dokładamy (po);
Pseudokod:
class kolejka }
{ int kolejka::push(int s)
class wezel {
{ wezel *nowy= new wezel;
public: nowy->w=s;
int w; if (!kon)
wezel *nast; {
}; pocz=nowy;
wezel *pocz; nowy->nast=NULL;
wezel *kon; kon=nowy;
public: return 1;
kolejka() }
{ kon->nast=nowy;
pocz=kon=NULL; nowy->nast=NULL;
} kon=nowy;
~kolejka(); return 1;
int push(int s); }
int pop(); int kolejka::pop()
}; {
kolejka::~kolejka() if (!pocz) return 0;
{ wezel *tmp=pocz;
wezel *tmp; pocz=pocz->nast;
while (pocz) int liczba=tmp->w;
{ delete tmp;
tmp=pocz; if(!pocz) kon=NULL;
pocz=pocz->nast; return liczba;
delete tmp; }
}
Kolejka priorytetowa (wykorzystanie kopca)
Kolejka priorytetowa jest strukturą danych, w której o zdjęciu elementu z kolejki nie
decyduje tylko kolejność umieszczenia elementu w kolejce, ale tak\
e priorytet. Pierwszy
zostanie obsłu\
ony ten element, który ma największy priorytet. Mo\
liwe sÄ… dwie metody
realizacji kolejki priorytetowej. W pierwszym przypadku mo\
na wykorzystać listę
jednokierunkowÄ… posortowanÄ…  najlepiej malejÄ…co. Wstawianie elementu do takiej
12
Algorytmy i struktury danych
struktury odbywa się na takich zasadach, jak zostały opisane wcześniej (patrz dodawanie
elementu do listy posortowanej). Jeśli nasza lista będzie posortowana malejąco względem
priorytetów to obsługiwać będziemy zawsze jako pierwszy element na początku listy. Dla
takiej struktury zło\
oność operacji wstawiania będzie wynosić O(n), a zło\
oność operacji
zdejmowania O(1).
Drugim sposobem implementacji kolejki priorytetowej jest wykorzystanie kopca. Aby
zaimplementować taką kolejkę nale\
y zapoznać się ze strukturą zwaną kopcem (opis
znajduje się w następnym punkcie). Przy wstawianiu elementu do kolejki nale\
y wykonać
dwie czynności. Dodać nowy element na pierwszej wolnej pozycji w kopcu i następnie
naprawić strukturę. Idę tej operacji przedstawią poni\
szy schemat.
60
Na zielono
zaznaczono element
20 56
nowo wstawiony.
Porównujemy go z
ojcem i je\
eli jest
większy to zamieniamy
18 9 1 76
miejscami.
60
Wykonujemy tÄ…
20 76
operacjÄ™ a\
dojdziemy
do korzenia, lub ojciec
będzie większy od
syna.
18 9 1 56
76
20 60
Gotowe
18 9 1 56
Kopiec
Kopiec to struktura drzewiasta posiadająca korzeń, od którego rozchodzi się potomstwo,
które przechowuje zawsze mniejsze wartości ni\
ich ojciec. Najwy\
ej w hierarchii kopca
znajduje się korzeń, który przechowuje element o największej wartości. Poni\
ej na
poszczególnych poziomach znajdują się kolejne elementy kopca  oczywiści rozmieszczone
zgodnie z zasadÄ…: elementy ni\
ej poło\
one sÄ… mniejsze od swojego rodzica. W kopcu
znajdujÄ… siÄ™ tak\
e elementy nie posiadajÄ…ce ju\
potomstwa. Określa się je mianem liści.
Kopiec mo\
emy zaimplementować na dwa sposoby. przechowujących pierwszym
przypadku powstaje on z węzłów przechowujących dane oraz dwa wskaz
niki do potomstwa
(do lewego i prawego syna  patrz rysunek poni\
ej). W drugim przypadku wykorzystujemy
tablice. Jeśli implementujemy kopiec w tablicy i indeksowanie elementów tablicy rozpoczyna
siÄ™ od 1 (np. Pascal) to wtedy indeks lewego syna obliczamy z wzoru 2i, a prawego z 21+1,
13
Algorytmy i struktury danych
gdzie i to indeks ojca. Natomiast indeks dziadka obliczymy z wzoru i/2, gdzie i to tak\
e
indeks ojca. Sytuacja wyglÄ…da nieco inaczej, gdy elementy tablicy sÄ… indeksowane od zera
(np. C/C++). W tym przypadku indeks lewego syna to 2i+1, prawego 2i+2, a indeks dziadka
to (i-1)/2, gdzie i to indeks ojca.
korzeń
100
20 60
18 9 56 33
11 15 7 8 21
liście
Naprawianie kopca
Zaczniemy nietypowo, bo nie od tworzenia struktury, lecz od jej naprawiania. A to
dlatego, \
e do tworzenia kopca będzie potrzebna umiejętność jego naprawienia. Je\
eli
zakładamy, \
e lewy podkopiec i prawy podkopiec są prawidłowe, natomiast problem
stanowi korzeń, który burzy strukturę kopca (nie przechowuje elementu największego).
Nale\
y naprawić tak popsutą strukturę. Naprawianie odbywa się w sposób rekurencyjny,
poczÄ…wszy od korzenia. Schemat tej operacji ilustrujÄ… poni\
sze rysunki.
1
Z ojca i synów
wybieramy element
maksymalny, i je\
eli
nie jest nim ojciec to
20 60
zamieniamy elementy,
i wywołujemy
naprawianie dla
fragmentu kopca,
18 9 56 33
którego korzeniem
znów jest niewłaściwy
element.
14
Algorytmy i struktury danych
60
Wykonujemy ta samÄ…
operacjÄ™ ponownie,
wywołując funkcję
napraw rekurencyjnie
20 1
dla podkopca
zakreślonego
kreskowanÄ… liniÄ….
18 9 56 33
60
Te same czynności
wykonujemy dopóty,
dopóki rozpatrywany
podkopiec będzie
20 56
nieprawidłowy lub nie
doszliśmy do
najni\
szego elementu
w kopcu.
18 9 1 33
Kopiec jest ju\

prawidłowy.
Tworzenie kopca
Zajmiemy się sytuacją, w której mamy w strukturze kopca (np. w tablicy)
umieszczone wartości w sposób przypadkowy. Teraz sytuacje jest nieco trudniejsza, gdy\

nie tylko element w korzeniu jest nieprawidłowo umieszczony, ale cały kopiec jest z
le
skonstruowany. Nale\
y więc utworzyć cały kopiec. W tym celu skorzystamy z omówionej
przed chwilÄ… metody naprawiania kopca. Wykonujemy operacje naprawiania kopca dla
podkopców począwszy od podkopców umieszczonych najni\
ej w strukturze. Schemat tej
operacji przedstawiajÄ… poni\
sze rysunki.
7
Wykonujemy operacjÄ™
10 13
napraw dla tych
kopców. Zawsze
zaczynamy od kopców
najni\
ej poło\
onych i
18 49 3
poruszamy się w górę.
15
Algorytmy i struktury danych
7
Wykonujemy operacjÄ™
49 13
napraw dla podkopca
poło\
onego wy\
ej (w
tym przypadku jest to
cały kopiec).
18 10 3
49
Gotowe
18 13
7 10 3
Sortowanie danych
Jest wiele metod sortowania danych. Tu omawiamy kilka najpopularniejszych. Dobór
odpowiedniej metody zale\
y od wielu czynników. Są to m.in. rodzaj danych, ilość danych,
wspólne cechy charakterystyczne danych. Wszystkie metody sortowania opisane w tym
opracowaniu są przedstawione na przykładzie sortowania tablicy liczb.
Sortowanie przez wstawianie (ang. insertion sort)
Zakładamy, \
e pierwszy element tablicy jest posortowany. Bierzemy kolejny,
przenosimy do zmiennej pomocniczej (tmp) i porównujemy elementy ju\
posortowane z
tmp. Jeśli te elementy są większe od tego w tmp, to przesuwamy je o jedną pozycję w prawo.
Na końcu (po zakończeniu przesuwania) wstawiamy element z tmp do pozostałej komórki
tablicy. ZÅ‚o\
oność tego algorytmu wynosi O(n2).
Algorytm ten ma swoje zalety, ale tak\
e wady. Plusem jest fakt, \
e sortuje on tylko
tablice wtedy, gdy jest to potrzebne. Jeśli nasza tablica będzie ju\
posortowana (mo\
e to być
część tablicy), to działanie algorytmu polega jedynie na pobraniu wartości do zmiennej tmp i
odstawieniu jej na miejsce. Nie wykonujemy \
adnych przesunięć. Minus dotyczy sytuacji,
kiedy liczby, które znajdowały się ju\
na odpowiednich pozycjach sÄ… i tak przesuwane. W
poni\
szym przykładzie ma to miejsce dla liczby 7, która w tablicy wejściowej zajmowała 2
pozycję i pomimo przesunięć, w ostateczności powróciła na 2 pozycję. Tak\
e podczas
wstawiania liczby do tablicy nale\
y przesunąć wszystkie większe (mniejsze) elementy w
prawo. Mo\
e się zdarzyć, \
e będzie trzeba przesunąć wszystkie elementy w tablicy.
Algorytm ten wykonuje się w n-1 krokach (gdzie n to ilość elementów do
posortowania), a w ka\
dym kroku wykonujemy jeszcze pewną ilość przesunięć  zale\
nÄ… od
poło\
enia sortowanej liczby. Mo\
liwe są dwa skrajne przypadki: tablica całkowicie
posortowana i tablica posortowana w odwrotnej kolejności oraz przypadek pośredni, gdy
elementy tablicy są rozmieszczone przypadkowo. W pierwszym skrajnym przypadku ilość
kroków będzie równa n-1, a ilość przesunięć w ka\
dym kroku 0 (liczba będzie porównana i
wstawiona w to samo miejsce). Zatem zło\
oność w tym przypadku wyniesie O(n). W
16
Algorytmy i struktury danych
drugim skrajnym przypadku ilość korków wyniesie tak\
e n-1, natomiast w ka\
dym k-tym
kroku będzie wykonane k przesunięć. Zatem ilość przesunięć w n-1 krokach wyniesie:
n -1
n (n - 1)
2
k = 1 + 2 + ... + (n - 1) = = O (n )
"
2
k =1
Obliczenia dla pośredniego przypadku doprowadziły do wyniku zbli\
onego do zło\
oności
O(n2). Zatem taką zło\
oność przyjmuje się dla tego algorytmu.
13 7 10 4 9
tmp
Krok 1 13 10 4 9 7
Krok 2 7 13 4 9 10
Krok 3 7 10 13 9 4
Krok 4 4 7 10 13 9
4 7 9 10 13
Czerwone pola to część posortowana tablicy.
Sortowanie przez wybór (ang. selection sort)
Przeszukujemy podtablicę w celu znalezienia minimum, jeśli jest mniejszy od
pierwszego nieposortowanego elementu w tablicy to zamieniamy je miejscami (na poczÄ…tku
to będzie pierwszy element tablicy). Elementy zamienione miejscami tworzą część
posortowaną tablicy. Czynność tą wykonujemy n-1 razy, gdzie n to ilość liczb w tablicy.
ZÅ‚o\
oność tego algorytmu tak\
e wynosi O(n2).
Musimy więc wykonać n-1 kroków (n to ilość elementów w tablicy), a w ka\
dym
kroku wykonujemy przeszukanie podtablicy o (n-1)-k elementach (k to numer kroku). Zatem
suma porównań jakie trzeba wykonać będzie wynosić:
n - 2
n (n - 1)
2
(n - 1) - k = (n - 1) + (n - 1) - 1 + ... + 1 = = O (n ) s
"
2
k = 0
Daje to zło\
oność algorytmu równą O(n2).
13 7 10 4 9
Krok 0 13 7 10 4 9
Krok 1 4 7 10 13 9
Krok 2 4 7 10 13 9
Krok 3 4 7 9 13 10
4 7 9 10 13
4 7 9 10 13
Czerwone pola to część posortowana tablicy. Niebieskie- element minimalny.
Czarna otoczka to obszar, z którego wybieramy minimum.
Sortowanie bÄ…belkowe - wersja standardowa i ulepszona (ang.
bubble exchange sort)
Bierzemy ostatni element tablicy i porównujemy z poprzednim. Jeśli jest mniejszy to
zamieniamy pozycjami i porównujemy ten mniejszy znów z sąsiednim. Mo\
na to porównać
do bąbelków, które są l\
ejsze i idą w górę. Ostatni element tablicy wrzucamy do bąbelka.
Jeśli poprzedni jest mniejszy (l\
ejszy) to bąbelek zostawia większy element i zabiera ten
mniejszy (l\
ejszy). Porównuje go z kolejnym sąsiadem i znów to samo... Robimy tak długo,
a\
bąbelek nie dotrze do części posortowanej tablicy. Zło\
oność tego algorytmu wynosi
O(n2).
17
Algorytmy i struktury danych
Kolejne etapy sortowania
13 13 13 13 4 4 4 4 4 4 4 4
7 7 7 4 13 13 13 7 7 7 7 7
10 10 4 7 7 7 7 13 13 9 9 9
4 4 10 10 10 9 9 9 9 13 10 10
9 9 9 9 9 10 10 10 10 10 13 13
Czerwone pola to cześć posortowana tablicy. Niebieskie to bąbelek.
Algorytm ten mo\
na nieco ulepszyć. Mo\
e się zdarzyć tak, \
e elementy tablicy sÄ…
częściowo posortowane. Taka sytuacja jest przedstawiona w przykładowej tablicy:
1 3 5 8 4 2
Wtedy mo\
na tak zaimplementować algorytm, aby został on wcześniej zakończony. Jeśli
bąbelek przejdzie z dołu do góry i \
adne komórki nie zostaną zamienione miejscami to
oznacza to, \
e tablica jest ju\
posortowana. Pomimo, \
e pozostały nam jeszcze kroki do
końca, nie musimy ich ju\
wykonywać. Przy implementacji warto sobie wprowadzić
dodatkową zmienną logiczną, która na początku ka\
dego cyklu bąbelka będzie ustawiana na
false, a jakakolwiek zamiana miejscami elementów powoduje jej ustawienie na true. Shella
ten sposób będziemy mogli kontrolować, czy były dokonywane jakieś zamiany.
Jeśli rozpatrzymy ulepszoną wersję algorytmu, to w przypadku, gdy tablica będzie
posortowana zostanie wykonane n-1 porównań (n to ilość elementów w tablicy) i \
aden
element nie zostanie zamieniony. Zatem algorytm będzie miał zło\
oność O(n). W przypadku
pesymistycznym, gdy elementy sÄ… posortowane odwrotnie ni\
powinny być wykonamy n-1
kroków (n to liczba elementów w tablicy), a w ka\
dym kroku wykonamy (n-1)-k porównań.
W ten sposób ogólna liczba porównań wyniesie:
n -1
n (n - 1)
2
(n - 1) - k = (n - 1) + (n - 1) - 1 + ... + 0 = = O (n )
"
2
k = 0
ZÅ‚o\
oność w tym wypadku wynosi O(n2). W sytuacji, gdy elementy w tablicy są
rozmieszczone przypadkowo zło\
oność algorytmu tak\
e jest zbli\
ona do O(n2).
Sortowanie Shella (ang. shellsort)
Sortowanie polegajÄ…ce na podzieleniu tablicy na kilka podtablic. Dokonujemy tego
wybierajÄ…c liczby przeskakujÄ…c po tablicy (pierwotnej) co h pozycji. Ka\
dÄ… z tych h podtablic
sortujemy, zmniejszamy h i znów sortujemy kolejne (większe) podtablice. Operację tą
wykonujemy a\
będziemy mieli jedną tablicę do posortowania.
Do posortowania podtablic wykorzystujemy algorytm sortowania przez wstawianie,
ewentualnie bÄ…belkowe. Wynika to z faktu, \
e co krok algorytmu nasza tablica będzie  coraz
bardziej posortowana , a algorytmy te sÄ… tym bardziej efektywne, im bardziej jest
 posortowana tablica wejściowa. Nie wolno wykorzystywać sortowania przez wybór, gdy\

wtedy zło\
oność sortowania wzrośnie do O(n2).
Przykład:
7 5 1 8 4 2 3 9 2 1 6 4
Ustalamy, \
e sortujemy co 3 (h=3). Podzielone podtablice zaznaczam na ró\
ne kolory.
7 5 1 8 4 2 3 9 2 1 6 4
18
Algorytmy i struktury danych
Sortujemy liczby w podtablicach.
Posortowane podtablice wyglądają następująco.
1 4 1 3 5 2 7 6 2 8 9 4
Sortujemy co h=2.
1 4 1 3 5 2 7 6 2 8 9 4
Sortujemy liczby w podtablicach.
Posortowane podtablice wyglądają następująco.
1 2 1 3 2 4 5 4 7 6 9 8
A teraz co h=1.
1 2 1 3 2 4 5 4 7 6 9 8
Sortujemy liczby w tablicy.
Posortowana tablica wygląda następująco.
1 1 2 2 3 4 4 5 6 7 8 9
Uwaga: Efekt tego sortowania jest widoczny tylko dla większej ilości elementów.
Stwierdzono, \
e je\
eli pierwszy krok będzie sortował co (16n/Ą)1/3, a drugi co 1 to
zło\
oność takiego algorytmu będzie wynosić O(n5/3). Jednak, aby uzyskać zło\
oność O(n5/4)
kroki nale\
y dobierać wg zasady Knutha. Ostatni krok jest zawsze równy zero, a ka\
dy
poprzedni powstaje z pomno\
enia go przez 3 i dodania 1. Dodatkowo nale\
y dobrać
pierwszy (h ) krok tak, \
e krok h byłby większy lub równy liczbie n (ilość elementów w
k k+2
tablicy).
h =1
1
h =3h +1
i i-1
h (początkowe) musi być tak dobrane, aby h e" n, gdzie n to ilość liczb do
k k+2
posortowania.
Ustalanie kroku poczÄ…tkowego obrazuje poni\
szy przykład:
mamy n=1000 liczb.
h będzie wynosić: 1,4,13,40,121,364,1093,&
i
Pierwszy krok h dobieramy zgodnie z podanym warunkiem, a więc będzie to 121 poniewa\

5
h jest ju\
większe od 1000 (1093). Nale\
y zauwa\
yć, \
e minimalna ilość liczb musi być
7
równa przynajmniej 13. Dla mniejszej tablicy stosujemy sortowanie przez wstawianie od
razu dla całej tablicy. Zło\
oność tego algorytmu jest lepsza od O(n2), ale ciągle brakuje jej do
osiągnięcia zło\
oności O(nlnn).
Sortowanie przez kopcowanie (ang. heapsort)
Do tego algorytmu wykorzystywana jest struktura zwana kopcem (omówiona w
rozdziale Kopiec). Aby posortować elementy nale\
y wykonać szereg operacji w kolejności
przedstawionej na schemacie. Algorytm ten ma zło\
oność rzędu O(nlnn).
19
Algorytmy i struktury danych
Mamy losowy zbiór liczb.
Tworzymy z nich kopiec.
Zamieniamy element znajdujÄ…cy siÄ™
w korzeniu z ostatnim elementem w
kopcu.
Elementy przenoszone na koniec
kopca tworzą część posortowaną (nie
wchodzÄ…cÄ… ju\
w skład kopca)
Naprawiamy pozostały
kopiec (bez elementów ju\

posortowanych).
Schemat 1: Sortowanie przez kopcowanie.
Sortowanie szybkie  wersja standardowa oraz z losowym
elementem dzielÄ…cym (ang. quicksort)
Dzielimy danÄ… tablicÄ™ liczb na dwie podtablice, gdzie ka\
dy element pierwszej
podtablicy będzie nie większy od ka\
dego elementu drugiej. To samo robimy z ka\
dÄ…
podtablicÄ… z osobna (rekurencyjnie) a\
uzyskamy tablice jednoelementowe. Aby było
mo\
liwe podzielenie tablicy nale\
y wybrać element wg którego będziemy dokonywać
podziału. Mo\
na wybrać pierwszy element tablicy (tak jak w poni\
szym przykładzie), ale
mo\
na równie\
wybrać losowo element z tablicy. Drugi wariant zabezpiecza nas to przed
sytuacją, w której nasza tablica do posortowania będzie prawie uporządkowana. Wtedy
wybranie losowego elementu spowoduje w miarę równomierny podział na podtablice.
Dzięki losowemu składnikowi nie stracimy na efektywności algorytmu.
Do podziału na podtablice wykorzystujemy dwa wskaz
niki: niebieski i czerwony.
Pierwszy przesuwamy w lewo dopóty, dopóki wskazuje na element większy lub równy
elementowi dzielÄ…cemu. Czerwony wskaz
nik przesuwamy w prawo a\
nie napotka na
element większy lub równy elementowi dzielącemu. Jeśli wskaz
niki się nie minęły to
zamieniamy miejscami elementy na które wskazują wskaz
niki i przesuwamy je dalej. Jeśli się
miną to tablica zostanie podzielona na dwie części. Dla ka\
dej podtablicy wykonujemy to
samo.
20
Algorytmy i struktury danych
4 5 1 8 7 3 2
2 5 1 8 7 3 4
2 3 1 8 7 5 4
2 3 1 8 7 5 4
1 3 2 4 7 5 8
1 3 2 4 7 5 8
OK OK
2 3 4 7 5
Niebieski poza
zakresem
2 3 4 7 5
OK OK OK
5 7
OK OK
1 2 3 4 5 7 8
Najgorsza sytuacja nasz czeka, gdy w ka\
dym przypadku jako element dzielÄ…cy
wybierzemy element najmniejszy (największy) z tablicy. Wtedy zło\
oność takiego algorytmu
wyniesie O(n2). Gdy będziemy mieć szczęście to ka\
da podtablica podzieli się zawsze na pól.
W tym optymistycznym wariancie zło\
oność wyniesie O(nlnn). W sytuacji pośredniej
oczekiwana zło\
oność algorytmu wynosi O(nlnn).
Sortowanie przez scalanie (ang. mergesort)
Sortowanie wykorzystujÄ…ce rekurencjÄ™. ZÅ‚o\
oność tego algorytmu wynosi O(nlnn).
Dzielimy tablicę z liczbami na 2 podtablice. Te podtablice znów dzielimy na dwie. Czynność
tą wykonujemy do uzyskania tablic jednoelementowych. Innymi słowy wykorzystujemy
metodÄ™ dziel i rzÄ…dz
. Dzielimy problem, którego nie potrafimy rozwiązać na mniejsze. Te
małe problemy są ju\
tak proste, \
e ich rozwiązanie nie sprawia nam problemów. Po
podzieleniu tablicy scalamy te podtablice jednocześnie sortując. Sortowanie odbywa się
poprzez zastosowanie pewnego schematu scalania tablic. Mam dwie podtablice: pierwsza
ma 0-n elementów i jest indeksowana zmienną a, druga ma 0-m elementów i jest
indeksowana zmiennÄ… b oraz tablice wynikowÄ… (scalonÄ…) o n+m elementach  indeksowanÄ…
zmiennÄ… c.
21
Algorytmy i struktury danych
N
Jeśli pod tab1[a] i pod
tab2[b] sÄ… liczby
T
N
Jeśli tab1[a] jest
mniejsze od tab2[b]
T
tabw[c++]=tab1[a++] tabw[c++]=tab2[b++]
Skopiuj do tabw elementy
pozostałe w tab1 lub tab2.
Schemat 2: Sortowanie przez scalanie.
Sortowanie przez zliczanie (ang. counting sort)
Je\
eli posiadamy pewne informacje na temat sortowanych elementów, np. wiemy, \
e
liczby mogące pojawić się w ciągu są ze skończonego zbioru liczb całkowitych, to mo\
emy
zmniejszyć jeszcze bardziej zło\
oność algorytmu sortowania.
Rozwa\
my to na przykładzie:
Mamy tablice nieposortowanych liczb. Wiemy dodatkowo, \
e sÄ… to liczby naturalne z
przedziału <0,3>.
1 2 0 1 2 3 3 1 1
Aby posortować te liczby tworzymy dodatkową tablicę (TabPom) o dokładnie takiej liczbie
komórek jak ilość liczb mieszcząca się w przedziale k "< 0,3 > . Dla naszego przykładu
będzie to tablica 4 elementowa (w przypadku implementacji w C/C++ indeks tablicy
odpowiada liczbie). Teraz nale\
y przebiec tablice wejściową (nieposortowaną) i zliczyć ilość
wystąpień poszczególnych liczb w tej tablicy a wynik wstawić do tablicy pomocniczej pod
odpowiednim indeksem.
TabPom [k ] = Ilosc (k )
W naszym przykładzie TabPom będzie wyglądać następująco:
1 4 2 2
0 1 2 3
Teraz nale\
y uzupełnić tablicę wyjściową liczbami ju\
posortowanymi. PoczÄ…wszy od
początku (od końca dla sortowania malejącego) wstawiamy taką ilość ka\
dej liczby jak jest to
zapisane w tablicy TabPom.
Otrzymamy tablicÄ™ liczb:
0 1 1 1 1 2 2 3 3
22
Algorytmy i struktury danych
ZÅ‚o\
oność takiego algorytmu sortowania jest równa O(n), co pozwala niezwykle szybko (w
porównaniu do innych algorytmów sortowania) posortować dane.
Sortowanie stabilne
Sortowanie stabilne to taki rodzaj sortowania, który zachowuje kolejność elementów
o tej samej wartości w ciągu wejściowym i wyjściowym. Innymi słowy ma znaczenie, który z
elementów o tej samej wartości będzie pierwszy. Dla omówionego wcześniej przypadku
zastosujemy sortowanie stabilne. Do cyfr o tej samej wartości dopisano indeksy, które mówią
o kolejności wystąpienia tych samych cyfr w tablicy wejściowej.
Przed:
1A 2A 0A 1B 2B 3A 3B 1C 1D
Po:
0A 1A 1B 1C 1D 2A 2B 3A 3B
Przepis implementacyjny:
wyzerowanie komórek tablicy TabPom
od początku tablicy wejściowej do n-1 elementu
TabPom[TabWej[i-ty_element]]++;
/*Zamiana ilości wystąpień liczby na pozycje, pod którą ma się znalez
ć w TabWyn*/
TabPom[pierwszy_element]--;
od drugiego elementu do ostatniego elementu tablicy TabPom
TabPom[i-tego_elementu] += TabPom[(i-1)-tego_elementu];
od n-1 do 0{
TabWyn[TabPom[TabWej[i-ty_element]]]=TabWej[i-ty_element];
TabPom[TabWej[i-ty_element]]--;}
Sortowanie pozycyjne (ang. radix sort)
Problem sortowania ciągów znaków lub liczb wielocyfrowych mo\
na rozwiązać
wykorzystujÄ…c sortowanie pozycyjne. Sortowanie to odbywa siÄ™ w grupach od lewej do
prawej lub odwrotnie. Jeśli chcemy posortować ciąg znaków (np. nazwiska) sortować
będziemy od lewej do prawej, natomiast aby posortować liczby poruszmy się w odwrotnym
kierunku.
Rozwa\
amy dla przykładu liczby trzy cyfrowych, które nale\
y posortować rosnąco.
Wykorzystując stabilne sortowanie przez zliczanie sortujemy względem liczb na
poszczególnych pozycjach. Wbrew pozorom sortowanie rozpoczynamy od pozycji najmniej
znaczących (jedności) i poruszamy się w  lewo . W pierwszym kroku sortujemy liczby
sugerujÄ…c siÄ™ jedynie ostatnia cyfrÄ…, w drugim kroku przedostatniÄ…, a w ostatnim kroku
bierzemy pod uwagę jedynie pierwszą cyfrę. W ten sposób nasza tablica liczb zostanie
posortowana. Warto równie\
zauwa\
yć, \
e jeśli któraś z liczb ma mniejszą ilość cyfr to
nale\
y z przodu uzupełnić ją zerami. Dokładny opis jednej z technik sortowania
pozycyjnego opisano w punkcie sortowanie kubełkowe (ang. bucket sort).
23
Algorytmy i struktury danych
Przykład:
Po Po Po
Przed
posortowaniu posortowaniu posortowaniu
sortowaniem
jedności dziesiątek setek
436 382 816 049
628 384 327 327
336 436 628 336
816 336 436 382
496 816 336 384
382 796 049 436
049 327 382 496
327 628 384 628
384 049 496 816
ZÅ‚o\
oność takiego algorytmu wynosi kn, gdzie k to ilość cyfr w liczbie, co daje w notacji
 wielkie O zło\
oność O(n).
Sortowanie kubełkowe (ang. bucket sort)
Jest to metoda pozwalająca posortować liczby całkowite. Do tego celu wykorzystamy
10 kubełków ponumerowanych od 0 do 9. Do ka\
dego będziemy wkładać odpowiednio
liczby. Na początku umieszczamy liczby w kubełkach sugerując się cyfrą jedności.
Przykładowo, jeśli cyfra ta jest równa 0 to liczba taka trafi do kubełka zerowego, gdy 1 to do
kubełka pierwszego, itd. Wa\
na jest jednak kolejność liczb w kubełku. Muszą on bowiem
być tam umieszczane w kolejności wystąpienia w ciągu. Dlatego podczas implementacji
kubełka nale\
y skorzystać z kolejki. W ten sposób wejściowa względna kolejność liczb
zostanie zachowana. Następnie wyciągamy elementy z kubełka i układamy w ciąg. Wa\
ne
jest aby wyciągać je począwszy od kubełka zerowego a\
po kubełek dziewiąty. Uzyskany
ciąg liczb znów rozrzucamy do kubełków, ale ju\
względem kolejnej cyfry (dziesiątek).
Operacje powtarzamy k razy (k to ilość cyfr w najdłu\
szej liczbie). Rozwa\
my ciÄ…g liczb: 436,
124, 068, 348, 741, 041, 002, 675, 943, 179.
Krok 1:
041
741 002 943 124
0 1 2 3 4
348
675 436 068 179
5 6 7 8 9
Otrzymamy: 741, 041, 002, 943, 124, 675, 436, 068, 348, 179
24
Algorytmy i struktury danych
Krok 2:
348
943
002 124 436 041
741
0 1 2 3 4
179
068 675
5 6 7 8 9
Otrzymamy: 002, 124, 436, 741, 041, 943, 348, 068, 675, 179
Krok 3:
068
041 179
002 124 248 436
0 1 2 3 4
675 741 943
5 6 7 8 9
Otrzymamy: 002, 041, 068, 124, 179, 436, 675, 741, 943
Najlepiej wykorzystać do zaimplementowania kolejki zrealizowane na tablicy (patrz
punkt Kolejka), gdy\
przyspiesza ona szybkość wykonywania. W tego typu implementacji
nie jest marnowany czas na operacje zwiÄ…zane z tworzeniem i destrukcjÄ… kolejek  raz
utworzone kolejki pozostajÄ…. Jedynie sÄ… wykonywane operacje zwiÄ…zane z przenoszeniem
danych między kolejkami. Ta wersja nie sprawdza się w przypadku du\
ych ciągów
elementów, gdy\
niezbędne jest k (ilość pozycji w elemencie  np. cyfr) tablic o rozmiarze n
(ilość elementów) oraz tablica wejściowa z danymi. Zło\
oność tego algorytmu jest rzędu
O(n).
Algorytmy rekurencyjne
Czasami problem mo\
na rozło\
yć na coraz to prostsze, których rozwiązanie nie
wymaga wysiłku lub wymaga bardzo małego wysiłku. Rozwiązujemy te proste problemy
wracajÄ…c siÄ™ do coraz trudniejszych, a\
oka\
e siÄ™, \
e główny (wyjściowy) problem został
rozwiÄ…zany. Nazywa siÄ™ to metodÄ… dziel i rzÄ…dz
. Metoda ta, z pozoru mo\
e dziwna, często
okazuje siÄ™ bardzo skuteczna, a niekiedy nawet jedyna.
25
Algorytmy i struktury danych
Proste algorytmy rekurencyjne
Silnia
Do obliczania silni mo\
na wykorzystać rekurencję. Aby obliczyć silnię z n wystarczy
obliczyć silnię z n-1 i pomno\
yć przez n. Następnie do obliczenia silni z n-1 znów
rozkładamy to na n-2 silnia razy n-1. W końcu dojedziemy do sytuacji, w której trzeba będzie
obliczyć silnie z 1, a to jest właśnie ten prostszy problem, który nie wymaga od nas wysiłku 
silnia z 1 jest równa jeden.
n! = (n-1)! * n
Przykład:
Mamy obliczyć silnię z 5.
" 5!=(5-1)! * 5
" (5-1)! = 4! = (4-1)! * 4
" (4-1)! = 3! = (3-1)! * 3
" (3-1)! = 2! = (2-1)! * 2
" (2-1)! = 1! = 1
Zagłębiamy się tak długo, a\
dojdziemy do problemu, który potrafimy rozwiązać (na
niebiesko). Następnie wracamy się powrotem. Wiedząc ile wynosi 1! umiemy obliczyć 2!.
Wiedząc ile wynosi 2! Umiemy obliczyć 3! itd. W ten sposób udało się obliczyć silnie z 5.
NWD  największy wspólny dzielnik (algorytm Euklidesa)
Problem rozwiÄ…zujemy podobnie jak w przypadku silni  rekurencyjnie. Nale\
y
skorzystać tutaj z wzoru:
NWD(x,y) = NWD(y,x % y) dla x>y
NWD(y,x) = NWD(x,y % x) dla y>x
%- dzielenie modulo.
Rozkładamy problem na mniejsze według tego wzoru do mementu, a\
gdy drugi z
argumentów osiągnie wartość zero.
Przykład:
Mamy obliczyć NWD dla 26 i 8.
" Obliczamy NWD dla 8 i (26%8)=2
" Obliczamy NWD dla 2 i (8%2)=0
Gdy druga z liczb będzie równa zero to pierwsza jest NWD. Zatem NWD dla 26 i 8 wynosi 2.
Wypisywanie wyrazu od końca
Kolejny problem, który pomo\
e nam rozwiązać rekurencja. Aby rozwiązać to zadanie
rozbijamy je na dwie części: próbujemy wypisać w odwrotnej kolejności wszystko z
wyjątkiem pierwszego znaku oraz na końcu wypisujemy wspomniany pierwszy znak
wyra\
enia. Jak wypisać wszystko z wyjątkiem pierwszego znaku. Znów robimy tak samo.
Przykład:
Wypisz od końca słowo:  notatka
" wypisujemy od końca  otatka i na końcu  n
" wypisujemy od końca  tatka i na końcu  o
" wypisujemy od końca  atka i na końcu  t
" &
" wypisujemy od końca  a i na końcu  k
26
Algorytmy i struktury danych
Rozbijając problem w ten sposób mo\
na go w bardzo prosty sposób wykonać. Nie sprawia
nam problemu wypisanie pojedynczego znaku od końca, a na takie właśnie części
rozło\
yliśmy nasze zadanie.
Algorytmy zachłanne (ang. greek algorithm)
Algorytmy te nie przewidują tego, co będzie  potem . Interesuje ich tylko  teraz .
Innymi słowy postępują zachłannie. Takie działanie nie zawsze okazuje się najlepsze, ale
bywa te\
idealne.
Problem kasjera
Mając następujący system monetarny: 1, 2, 5, 10, 20, 50 wydajemy resztę w taki
sposób, aby stracić jak najmniej monet. Postępując zgodnie z zasadami algorytmu
zachłannego za ka\
dym razem będziemy wydawać monety o największym nominale.
Doprowadzi nas to do optymalnego rozwiązania  wydamy najmniejszą ilość monet.
Przykład:
Wydać 79 złotych.
" wydajemy 50, zostaje 29zł
" wydajemy 20, zostaje 9zł (gdy\
50 się nie da  nie chcemy być stratni :&)
" wydajemy 10, zostaje 9zł
" wydajemy 5, zostaje 4zł
" wydajemy 2, zostaje 2zł
" wydajemy 2, zostaje 0zł
StosujÄ…c powy\
szą metodę wydaliśmy 6 monet.
Odpowiednie dobranie nominałów w systemie monetarnym okazuje się nie bez
znaczenia. Zastanówmy się co by było, gdybyśmy posługiwali się systemem monetarnym: 1,
10, 20, 25. W tym przypadku algorytm zachłanny nie zadziała optymalnie.
Przykład:
MajÄ…c system: 1, 10, 20, 25.
Wydać 31 złotych.
" wydajemy 25, zostaje 6zł
" wydajemy 1, zostaje 5zł
" wydajemy 1, zostaje 4zł
" wydajemy 1, zostaje 3zł
" wydajemy 1, zostaje 2zł
" wydajemy 1, zostaje 1zł
" wydajemy 1, zostaje 0zł
Wydaliśmy 7 monet, co nie jest minimalną liczbą monet. Mo\
na było wydać 20 + 10 + 1 co
daje trzy monety. W tym przypadku algorytm zachłanny nie zadziałał optymalnie.
Szukanie minimum funkcji
Problem ten mo\
na rozwiązać na wiele sposobów. Jeden z nich polega na obliczeniu
wartości funkcji dla pewnej liczby (argument od którego rozpoczniemy poszukiwanie) i
następnie obliczaniu kolejnych wartości dla argumentów powiększonych o pewien krok.
Robimy to dopóty, dopóki wartości funkcji się zmniejszają. Jeśli kolejna wartość będzie
większa od poprzedniej, to cofamy się do poprzedniego kroku  to jest nasze minimum
lokalne funkcji.
27
Algorytmy i struktury danych
Strategia  dziel i rzÄ…dz

Poni\
ej jeszcze kilka innych algorytmów wykorzystujących metodę dziel i rządz
.
Wszystkie omówione problemy udało się rozwiązać dzięki rozło\
eniu ich na mniejsze,
prostsze.
Wyznaczanie wartości maksymalnej
Nale\
y znalez
ć wartość maksymalną w ciągu liczb. Rozwiązanie problemu
rozpoczynamy od podziału ciągu na 2 równe (ewentualnie zbli\
one  nieparzysta ilość liczb)
części. W ka\
dej z nich szukamy minimum i następnie z tych 2 minimów wybieramy jedno
(mniejsze  \
eby nie było wątpliwości :&). Jak znalez
ć minimum w podtablicach? Tak samo
jak w tablicy głównej. Znów ka\
dą podtablice dzielimy na 2 części. I tak, a\
do uzyskania
tablic jedno elementowych. Znalezienie minimum w podtablicy jedno elementowej nie jest
trudne :&. WykorzystujÄ…c rekurencje i dzielÄ…c problem na mniejsze osiÄ…gniemy cel.
Linijka
Kolejny problem, który przy pomocy rekurencji mo\
na łatwo i szybko rozwiązać.
Chodzi o to, aby otrzymać efekt jak na poni\
szym rysunku.
Najpierw dzielimy odcinek na pół. Potem ka\
dą z połówek znów dzielimy na pól, przy
czym podziałka ma ju\
proporcjonalnie mniejszą długość. To samo robimy z ka\
dą ćwiartką,
itd. Operacje wykonujemy rekurencyjnie. Nale\
y ograniczyć wywołania rekurencyjne, aby
umo\
liwić zakończenie podziału. Dla powy\
szego rysunku wykonaliśmy podział stopnia
czwartego. Długość odcinka dzielącego mo\
na uzale\
nić od kroku (stopnia zagłębienia)
rekurencji.
Wie\
a Hanoi
Problem polega na tym, aby przeło\
yć n krą\
ków z słupka A na słupek B w taki
sposób, aby w trakcie tej operacji większy krą\
ek nigdy nie został poło\
ony na mniejszym.
KrÄ…\
ki nale\
y przekładać pojedynczo. Operację tę znów sprowadzamy to prostszych
problemów. Przenosimy n-1 krą\
ków (wszystkie z wyjątkiem ostatniego - największego) na
wie\
e B, przekładamy największy krą\
ek na wie\
e C. Aby przenieś pozostałe n-1 krą\
ków
znów dzielimy problem podobnie. Operacje jakie nale\
y wykonać, aby przenieś n krą\
ków
opisuje poni\
szy pseudo kod.
Przepis implementacyjny:
przenieÅ› (n_krÄ…\
ków, od_wie\
y, do_wie\
y, tmp_wie\
a)
{
jeśli są krą\
ki
{
przenieÅ›(n-1_krÄ…\
ków,od_wie\
y,tmp_wie\
a,do_wie\
y)
przełó\
krÄ…\
ek od_wie\
y do_wie\
y
przenieÅ›(n-1_krÄ…\
ków,tmp_wie\
a,do_wie\
y,od_wie\
a)
}
}
28
Algorytmy i struktury danych
A B C
CiÄ…g liczb Fibonacciego
Problem polega na obliczeniu n kolejnych liczb tzw. CiÄ…gu Fibonacciego. Jest to ciÄ…g,
w którym pierwsza liczba jest równa 0, a druga 1. Ka\
da kolejna powstaje z sumy dwóch
poprzednich liczb. 0, 1, 1, 2, 3, 5, 8, 13, 21,& Problem ten rozwiÄ…zujemy wykorzystujÄ…c
rekurencjÄ™. Warto jednak zauwa\
yć, \
e obliczając kolejne liczby ciągu powtarzamy niektóre
obliczenia. Poni\
szy schemat obrazuje operacje jakie nale\
y wykonać, aby obliczyć 5 liczbę
ciągu. Fragmenty zakreślone przerywaną linią oznaczają podwójnie liczone wyra\
enia. Im
dalsza liczba ciągu, tym powtarzanych operacji obliczeniowych jest coraz więcej.
5
4 3
3 2 2 1
2 1 1 0 1 0
1 0
Warto by się zastanowić, czy nie da się tego uniknąć. Rozwiązaniem jest zastosowanie
programowania dynamicznego. Obliczając kolejne elementy ciągu zapamiętujemy wyniki,
aby w przyszłości (gdy znów w kolejnych obliczeniach będą one nam potrzebne) móc z nich
skorzystać.
Programowanie dynamiczne
CiÄ…g liczb Fibonacciego
Zastosowanie programowania dynamicznego do rozwiązania tego problemu zostało
opisane w punkcie CiÄ…g liczb Fibonacciego w dziale Strategia  dziel i rzÄ…dz
 .
Liczba kombinacji  trójkąt Pascala
Problem polega na obliczenie liczby kombinacji, czyli ilości mo\
liwości wyboru r-
elementowych podzbiorów z n-elementowego zbioru. Matematycznie obliczenia takie
mo\
na wykonać korzystając ze wzoru:
n n!
ëÅ‚ öÅ‚
=
ìÅ‚ ÷Å‚
r r!Å"(n - r)!
íÅ‚ Å‚Å‚
29
Algorytmy i struktury danych
Do rozwiÄ…zania tego problemu u\
yjemy jednak innych wzorów i zale\
ności. Przedstawione
sÄ… one poni\
ej.
n
ëÅ‚ öÅ‚
= 1, jeśli r=0 lub n=r
ìÅ‚ ÷Å‚
r
íÅ‚ Å‚Å‚
n n
ëÅ‚ öÅ‚ ëÅ‚ -1 n -1
öÅ‚ ëÅ‚ öÅ‚
= + , dla 0ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚ ìÅ‚ ÷Å‚
r r r
íÅ‚ Å‚Å‚ íÅ‚ Å‚Å‚ íÅ‚ -1
Å‚Å‚
KorzystajÄ…c z powy\
szych informacji mo\
na zaimplementować algorytm pozwalający w
sposób rekurencyjny obliczyć liczbę kombinacji n po r. Warto zauwa\
yć, \
e tak\
e w tym
przypadku (podobnie jak miało to miejsce przy obliczaniu liczb Fibonacciego) niektóre
obliczenia będą wykonywane kilka razy. Warto więc wykorzystać idee programowania
dynamicznego. Obliczone wartości n po r zapamiętujemy w dwuwymiarowej tablicy, w
której indeks wierszy odpowiadać będzie wartościom n, a indeks kolumn  wartościom r.
n
ëÅ‚ öÅ‚
Tablice tą na starcie uzupełniamy informacjami, które ju\
znamy, tzn. wiemy, \
e = 1 i
ìÅ‚ ÷Å‚
0
íÅ‚ Å‚Å‚
n
ëÅ‚ öÅ‚
= 1. Pozostałe wartości będą uzupełniane w trakcie kolejnych obliczeń.
ìÅ‚ ÷Å‚
n
íÅ‚ Å‚Å‚
Problem pakowania plecaka (ang. knapsack problem)
Problem polegam na tym, aby spakować plecak x-kilogramowy rzeczami, które mają
swoją wagę i wartość w taki sposób, aby spakowane rzeczy były najbardziej wartościowe.
Suma wag wszystkich przedmiotów nie mo\
e przekraczać pojemności plecaka. Zakładamy
tak\
e, \
e mamy nieskończenie wiele rzeczy tego samego typu.
Gdybyśmy mogli dzielić pakowane rzeczy to problem byłby banalny. Wystarczyłoby
zapakować cały plecak tym samym rodzajem przedmiotów, których stosunek wartości do
wagi jest maksymalny. Jednak my nie mo\
emy podzielić naszych rzeczy (nie da się
spakować jednej nogawki spodni, bo po co nam to :&).
Rozwa\
my przykład:
Mamy 18 kg plecak i trzy rzeczy:
Pierwsza o wartości 10zł i wadze 10 kg;
Druga o wartości 4zł i wadze 5 kg;
Trzecia o wartości 3zł i wadze 4 kg.
Dane:
przedmiot p1 przedmiot p2 przedmiot p3
cena (zł) 10 4 3
waga (kg) 10 5 4
cena/waga 1 0.8 0.75
Mo\
emy plecak spakować na dwa przykładowe sposoby:
Pierwszy, gdy będziemy pakować zachłannie, tzn. będziemy wkładać do plecaka
rzeczy o największym stosunku c/w.
wkładamy rzecz p1, pozostaje nam 8 kg wolnego miejsca;
wkładamy rzecz p2, pozostaje nam 3 kg wolnego miejsca;
nie mo\
emy ju\
wło\
yć nic więcej;
nasz plecak ma wartość 10 zł + 4 zł = 14 zł;
Drugi sposób, który rozwa\
ymy to pakowanie, które nie opiera się na algorytmie
zachłannym.
30
Algorytmy i struktury danych
wkładamy rzecz p1, pozostaje nam 8 kg wolnego miejsca;
wkładamy rzecz p3, pozostaje nam 4 kg wolnego miejsca;
wkładamy rzecz p3, pozostaje nam 0 kg wolnego miejsca;
plecak jest pełen;
nasz plecak ma wartość 10 zł + 3 zł + 3 zł = 16 zł.
Nie trudno zauwa\
yć, \
e lepiej zabrać plecak drugi (ma większą wartość).
Jak to rozwiązać algorytmicznie w programie?
Najlepiej w tym celu wykorzystać rekurencję oraz programowanie dynamiczne.
Zaczynamy od plecaka 1 kg. Taki plecak jest bardzo łatwo spakować. Następnie pakujemy
plecak 2kg, 3kg i tak, a\
dojdziemy do plecaka x kilogramowego. Aby spakować plecak, np.
8kg, mo\
emy wybrać rzecz:
5kg i to, co mo\
emy spakować do plecaka 3 kilogramowego (8-5=3);
4kg i to, co mo\
emy spakować do plecaka 4 kilogramowego (8-4=4);
waga plecaka co wkładamy (w kg) wartość plecaka (zł)
1 --------------
2 --------------
3 --------------
4 4 (3zł) 3
5 (4zł) 4
5
4 (3zł) + 1. 3
5 (4zł) + 1. 4
6
4 (3zł) + 2. 3
5 (4zł) + 2. 4
7
4 (3zł) + 3. 3
5 (4zl) + 3. 4
8
4 (3zł) + 4. 6
5 (4zł) + 4. 7
9
4 (3zł) + 5. 7
10 (10zł) 10
10
5 (4zł) + 5. 8
4 (3zł) + 6. 7
10 (10zł) + 1. 10
11
5 (4zł) + 6. 8
4 (3zł) + 7. 7
10 (10zł) + 2. 10
12 5 (4zł) + 7. 8
4 (3zł) + 8. 9
10 (10zł) + 3. 10
13
5 (4zł) + 8. 10
4 (3zł) + 9. 10
10 (10zł) + 4. 13
14
5 (4zł) + 9. 11
4 (3zł) + 10. 13
10 (10zł) + 5. 14
15
5 (4zł) + 10. 14
4 (3zł) + 11. 13
10 (10zł) + 6. 14
16 5 (4zł) + 11. 14
4 (3zł) + 12. 13
17 10 (10zł) + 7. 14
5 (4zł) + 12. 14
31
Algorytmy i struktury danych
4 (3zł) + 13. 13
10 (10zł) + 8. 16
18
5 (4zł) + 13. 14
4 (3zł) + 14. 16
Na czerwono oznaczyłem pojemność plecaka, którego opcje pakowania trzeba wybrać dodatkowo(np. plecak 5kg
to 4kg i to co wkładamy do 1kg plecaka). Gdy dla danego plecaka mamy kilka opcji do wyboru to wybieramy
lepszÄ…, opcje na niebieskim tle.
Rozkład na czynniki pierwsze liczb naturalnych (0-1000)
Problem rozkładu liczb naturalnych z przedziału od 0 do 1000 na czynniki pierwsze
rozwiÄ…zujemy tak\
e korzystając z rekurencji i programowania dynamicznego. Rozkładając
kolejne liczby naturalne zapamiętujemy wynik tak, aby póz
niej móc z niego korzystać. Do
implementacji mo\
na wykorzystać tablice 1001 elementową (od 0 do 1000) wskaz
ników do
list przechowujących czynniki pierwsze, na które rozkładamy daną liczbę. Ka\
da lista będzie
tak naprawdę przechowywała jedną liczbę pierwszą, która wskazywać będzie na
odpowiedni indeks innej liczby w tablicy, jako na kolejne elementy listy.
Przykładowo, liczbę 12 rozkładamy na 2 razy to na, co rozło\
yliśmy liczbę 6. Sześć to:
2 razy to, na co rozło\
yliśmy 3. Poniewa\
liczba trzy jest liczbą pierwszą, więc to ju\
jest
koniec listy.
Metoda powrotów   prób i błędów (ang. backtracking)
Aby rozwiązać problem w trakcie jego rozwiązywania dokonujemy pewnych decyzji.
Wybieramy pewną drogę, którą będziemy dalej się poruszać. Mo\
e się zdarzyć sytuacja, w
której nasz wybór będzie zły i doprowadzi nas to do braku rozwiązania  nie osiągniemy
celu. Wtedy nale\
y cofnąć ostatnią decyzję i wybrać inną drogę, która być mo\
e doprowadzi
nas do celu. Taka metoda rozwiązywania problemu określana jest mianem metody
powrotów. Aby móc dokonać wspomnianych powrotów nale\
y zapamiętywać ruchy
(decyzje), których dokonaliśmy wcześniej, aby móc do nich powrócić. Rozwiązać to mo\
na
odkładając informacje o kolejnych naszych posunięciach na stos. Mo\
na wykorzystać tak\
e
implementację powrotów wykorzystującą rekurencję.
Problem skoczka szachowego
Zadanie polega na przeskoczeniu skoczkiem szachowym wszystkich pól
szachownicy. Zakładamy, \
e na ka\
dym polu mo\
emy stanąć tylko raz. Skoczek szachowy
mo\
e ośmiu danego miejsca wykonać skok w jednym z ośmiu kierunków. Mo\
liwości ruchu
skoczka pokazano na poni\
szym rysunku.
7 6
8 5
start
1 4
2 3
Zatem skaczÄ…c skoczkiem po planszy sprawdzamy, czy ju\
tu byliśmy, jeśli nie to stawiamy
skoczka w tym miejscu, jeśli tak, to nale\
y wycofać się z poprzedniego kroku ośmiu wybrać
innÄ… mo\
liwość. Podczas implementacji nale\
y wykorzystać rekurencję. Szachownicę
mo\
emy zaimplementować jako tabelę ośmiu wymiarach n+4 na n+4 (gdzie n to wymiary
planszy szachownicy). Ka\
de pole będzie przechowywać wartość 0  gdy jeszcze na nim nie
stanęliśmy i 1- gdy ju\
postawiliśmy tu skoczka. Dodatkowe cztery wiersze i kolumny to
tzw. Otoczka zabezpieczajÄ…ca. PoruszajÄ…c siÄ™ po wierszach i kolumnach tablicy nale\
y
zadbać o to, aby nie wyjść poza obszar pamięci przydzielony dla tej tablicy. Jednym z
32
Algorytmy i struktury danych
rozwiązań jest sprawdzanie przed ka\
dym skokiem, czy ma to miejsce. Drugim (które tu
zostało opisane) polega na otoczeniu naszej  szachownicy otoczką o grubości dwóch
wierszy (kolumn). Komórki tej otoczki będą ju\
na starcie przechowywały wartości jeden, co
uniemo\
liwi skok na te pola. Poni\
ej przedstawiono zawartość tabeli dla szachownicy 4 na 4
przed rozpoczęciem skoków.
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Przepis implementacyjny:
skocz_na_pozycje(x,y)
{
jeśłi jeszcze nie tu nie byłeś
{
inkrementuj ilość odwiedzonych pól;
zaznacz swoją obecność wstawiając do komórki 1;
jeśli ilość odwiedzonych pól jest równa
ilości pol na szachownicy
{
znaleziono rozwiÄ…zanie; koniec;
}
//rekurencyjne wywołanie funkcji
skocz_na_pozycje (x-1,y-2);
skocz_na_pozycje (x+1,y+2);
skocz_na_pozycje (x-1,y+2);
skocz_na_pozycje (x+1,y-2);
skocz_na_pozycje (x-2,y-1);
skocz_na_pozycje (x-2,y+1);
skocz_na_pozycje (x+2,y-1);
skocz_na_pozycje (x+2,y+1);
//gdy rekurencja powróci
zmniejsz ilość odwiedzonych pół;
wyma\
swoją obecnośc (wstaw do komórki 0)
}
}
Problem ośmiu hetmanów
Zadanie polega na rozstawieniu na szachownicy 8 hetmanów w taki sposób, aby
\
aden z nich nie znajdował się w tej samej kolumnie, wierszu i na tej samej przekątnej co
inny hetman. Jeśli przyjmiemy, \
e ka\
dy hetman będzie stał w innej kolumnie, to dla
ka\
dego z nich mamy 8 mo\
liwości ustawienia (poniewa\
mamy 8 wierszy do wyboru).
Rozpoczynamy stawiając pierwszego hetmana w pierwszym wierszu, następnie
przechodzimy do drugiej kolumny i próbujemy wstawić drugiego hetmana. Nie mo\
na tego
zrobić w pierwszym ani drugim wierszu, więc stawiamy go w trzecim. To samo robimy z
ka\
dym kolejnym hetmanem. Jeśli oka\
e siÄ™, \
e któregoś z nich nie da się ustawić w \
adnym
wierszu, musimy wycofać się z ostatniego ruchu  musimy powrócić. Zdejmujemy
poprzednio postawionego hetmana i szukamy dla niego kolejnego mo\
liwego wiersza.
Poni\
szy pseudo kod pozwala ustawić n hetmanów na planszy o wymiarach n na n.
33
Algorytmy i struktury danych
Przepis implementacyjny:
//Funkcję wywołamy w pętli od i=0 do n-1, gdzie n oznacza rozmiar planszy.
wstaw_hetmana(w i-tej kolumnie)
{
od j=0 do j=n-1
{
jeśli mo\
na wstawić hetmana na pozycji (j,i)
{
połó\
tam hetmana;
wywołaj funkcję wstaw_hetmana(i + 1);
zdejmij hetmana(gdy rekurencja  powróci );
}
}
}
CoÅ› na deser
Problemów, których rozwiązanie mo\
na znalez
ć rekurencyjnie jest wiele. Oprócz
omawianych powy\
ej sÄ… tak\
e takie, które umo\
liwiajÄ… uzyskanie wielu ciekawych dla oka i
nie tylko efektów. Poni\
ej opisano w skrócie na czym polegają te najbardziej popularne.
Krzywa Kocha (płatek śniegu)
Problem polega na narysowaniu krzywej, która powstaje według pewniej zasady. Na
początku mam odcinek. Dzielimy go na trzy części i w miejscu środkowej części rysujemy
trójkąt równoboczny bez podstawy. Następnie z ka\
dym z czterech odcinków robimy to
samo. Potem znów ka\
dy z odcinków dzielimy według tej zasady. Takie operacje podziału
mo\
emy wykonywać n-krotnie, co doprowadzi nas do uzyskania całkiem ciekawych
efektów wizualnych. Podziału tego mo\
emy dokonać tak\
e dla ka\
dego z boków dowolnej
figury. Uzyskane efekty będą jeszcze bardziej zachwycające.
Trójkąt i dywan Sierpińskiego
Problem polega na podziale trójkąta równobocznego na mniejsze, jednakowe
trójkąty. Dodatkowo trójkąty narysowane  do góry nogami będą namalowane w innym
kolorze. W ten sposób uzyskamy trójkąt wypełniony pewnego rodzaju mozaiką. Operacje
rozpoczynamy od podziału wyjściowego trójkąta na cztery mniejsze. W tym celu dzielimy
ka\
dy z boków trójkąta na pół i łączymy te punkty środkowe boków. Dla ka\
dego z
powstałych w ten sposób czterech trójkątów znów wykonujemy te samą operację. Czynność
powtarzamy n razy.
Krzywa Hilberta
Problem polega na narysowaniu krzywej (właściwie łamanej) powstającej według
określonego wzoru. Wyjściowym elementem jest łamana o poni\
szym kształcie.
34
Algorytmy i struktury danych
A
ącząc odpowiednio takie elementy ze sobą uzyskamy krzywą o specyficznym kształcie.
Mo\
na tego rodzaju krzywą wykorzystać np. do pseudolosowego przebiegania po pewnym
obszarze jak to ma miejsce w przypadku rozsiewania błędów podczas redukcji obrazu do 256
kolorów. Poni\
ej pokazano przykłady krzywych ró\
nego rzędu (po lewej- 2 rzędu, po prawej
4-rzędu).
Zliczanie białych obszarów i liczby białych pól w ka\
dym obszarze
Problem polega na zliczeniu ilości zakreślonych pól na planszy oraz ilości
zakreślonych obszarów  grup połączonych ze sobą pól. Niech nasza plansza będzie
przedstawiona w postaci tablicy n na n oraz 0 oznacza nie zakreślone pole, 1- zakreślone, a 2-
zliczone. Dodatkowo tablica musi mieć tzw. otoczkę , czyli dodatkowy wiersz(kolumnę) na
górze (po lewej) i na dole (po prawej). Otoczka ta uniemo\
liwi wyjście poza obszar pamięci
przeznaczony dla tablicy z planszÄ…. Problem tak\
e rozwiÄ…zujemy rekurencyjnie a pseudokod
(oraz przykładową planszę) pozwalający tego dokonać przedstawiono poni\
ej.
2 2 2 2 2 2 2 2 2 2
2 0 0 0 0 0 0 0 0 2
2 0 1 1 1 0 0 1 0 2
2 0 0 0 1 0 0 1 0 2
2 0 0 0 0 0 0 1 0 2
2 0 1 1 1 0 0 1 0 2
2 0 0 0 1 0 0 1 0 2
2 0 0 1 1 0 0 0 0 2
2 0 0 0 0 0 0 0 0 2
2 2 2 2 2 2 2 2 2 2
35
Algorytmy i struktury danych
Przepis implementacyjny:
//Deklarujemy funkcjÄ™ ile(i,j), gdzie i/j to nr wiersza/kolumny.
od i=1 do i=n-2
od j=1 do j=n-2;
wywołujemy funkcję ile(i,j)
{
jeśli nie byliśmy jeszcze na tym polu
{
skreślamy obszar (wstawiamy 2) aby zaznaczyć swoją obecność;
jeśli nasze pole nie jest obszarem zakreślonym to zwracamy 0
jeśłi pole jest obszarem zakreślonym to zwracamy 1 + ile(i-1,j) + ile(i+1,j) + ile(i,j-1) +
ile(i,j+1);
}
}
Drzewo binarne  implementacja podstawowych operacji
Drzewo to struktura umo\
liwiająca przechowywanie danych zbudowana z węzłów
oraz wskaz
ników do potomków. Drzewa rysuje się w sposób odwrotny, ni\
rosnÄ… one w
przyrodzie :&. Na szczycie struktury znajduje się korzeń  węzeł nie mający ojca, a na samym
dole umiejscowione są liście- nie posiadające synów. Odmianą drzew są drzewa binarne. Są
to struktury, w których ka\
dy węzeł posiada dwóch synów  lewego i prawego.
Rozmieszczenie elementów w drzewie nie jest przypadkowe. Wszystkie elementy znajdujące
siÄ™ w lewym poddrzewie sÄ… mniejsze od swojego ojca, natomiast elementy prawego
poddrzewa są większe od ojca. Reguła ta obowiązuje wszystkie poddrzewa. Przykładowo:
wszystkie elementy lewego poddrzewa piętnastki są mniejsze od niej, to samo ma miejsce
dla lewego poddrzewa siódemki oraz 4. Te same reguły obowiązują tak\
e dla wszystkich
prawych poddrzew  wartości w nich przechowywane muszą być większe od ojca.
15
7 30
4 13 25 34
2 28
Dodawanie elementu
Aby wstawić nowy element do drzewa nale\
y począwszy od korzenia porównywać
dany element z węzłem i je\
eli jest on mniejszy od wartości przechowywanej w tym węz
le to
poruszać się w lewo po drzewie, w przeciwnym wypadku poruszać się w prawo.
Wędrujemy tak długo, a\
dojdziemy do miejsca, w którym napotkany wskaz
nik do potomka
w węz
le będzie wskazywał na NULL. Wtedy wstawiamy nowy węzeł w to miejsce, a
wspomniany wskaz
nik ustawiamy tak, aby wskazywał na nowy węzeł.
36
Algorytmy i struktury danych
Przykład: do poni\
szego drzewa wstawiamy liczbę 23. Niebieską strzałką zaznaczono
kierunek poruszania siÄ™ po drzewie.
15
7 30
4 13 25 34
2 23 28
Wyszukiwanie elementu, element minimalny i maksymalny
Przeszukiwanie drzewa binarnego jest bardzo podobne do wstawiania.
Rozpoczynając od korzenia porównujemy wartość napotkanego węzła z szukaną liczbą. Gdy
to nie jest szukany element to, jeśli szukana liczba jest mniejsza od tej przechowywanej w
węz
le to idziemy w lewo, w przeciwnym wypadku poruszamy siÄ™ w prawo. Pomijanie
podczas przeszukiwania niektórych poddrzew mo\
liwe jest dzięki wspomnianemu ju\

wcześniej specjalnemu rozmieszczeniu elementów w drzewie. Je\
eli przejdziemy całe
drzewo (natkniemy siÄ™ na NULL) i \
adna napotkana wartość nie odpowiadała naszej liczbie,
to oznacza to, \
e liczby nie ma w szukanym węz
le.
Przykład: przeszukujemy drzewo dwa razy. Za pierwszym razem szukamy liczby 13, za
drugim razem sprawdzamy czy jest w nim liczba 22. Niebieska strzałka to kierunek
poruszania siÄ™ po drzewie w poszukiwaniu 13, czerwona- w poszukiwaniu 22. Ja siÄ™ oka\
e,
liczby 22 nie będzie w drzewie.
15
7 30
4 13 25 34
2 23 28
Je\
eli chcemy znalez
ć element minimalny (maksymalny) w drzewie to poruszamy się
maksymalnie w lewo (prawo). Na poni\
szym rysunku niebieska strzałka to poszukiwanie
minimum, czerwona- maksimum. Specyficzne rozmieszczenie elementów w drzewie
sprawia, \
e element minimalny znajduje się zawsze w najbardziej  wysuniętym na lewo
węz
le, a element maksymalny w najbardziej  wysuniętym na prawo węz
le drzewa.
37
Algorytmy i struktury danych
15
7 30
4 13 25 34
2 23 28
Usuwanie elementu (3 przypadki)
Nale\
y tutaj omówić trzy mo\
liwe przypadki, jakie mogą wystąpić podczas
usuwania elementu z drzewa binarnego. Pierwszy, to taki, kiedy usuwany węzeł nie ma
potomstwa. Jest to najprostsza sytuacja. Nale\
y usunąć ten element (zwolnić pamięć) i
zadbać o to, aby jego rodzic wskazywał teraz na Null.
Przykład: usuwamy węzeł przechowujący wartość 2.
15
7 30
4 13 25 34
2 23 28
Kolejna sytuacja to taka, w której usuwany węzeł posiada jednego potomka. Tutaj
nale\
y zadbać (oprócz zwolnienia pamięci) o to, aby rodzic usuwanego elementu wskazywał
teraz zamiast na usuwany element na jego potomka.
38
Algorytmy i struktury danych
Przykład: usuwamy węzeł przechowujący wartość 30.
15
7 30
4 13 25
23 28
Ostatnia z mo\
liwych sytuacji, to ta, w której usuwany węzeł posiada a\
dwóch potomków.
Aby usunąć taki węzeł nale\
y zamienić wartość z tego węzła z wartością minimalną w
prawym poddrzewie usuwanego węzła (na rysunku otoczone przerywaną linią) lub z
wartością maksymalną w lewym poddrzewie. Następnie usuwamy element minimalny w
prawym poddrzewie, ewentualnie maksymalny w lewym poddrzewie. Ta operacja ju\

została opisana w dwóch poprzednich przypadkach. Po takiej zamianie element minimalny
(maksymalny) nie będzie miał potomstwa lub co najwy\
ej będzie miał jedynie prawego
(lewego) syna.
Przykład: usuwamy węzeł przechowujący wartość 7.
Najpierw szukamy elementu minimalnego w prawym poddrzewie.
15
7 30
4 13 25
10 14 28
39
Algorytmy i struktury danych
Następnie zamieniamy usuwany element z tym znalezionym.
15
10 30
4 13 25
7 14 28
Teraz usuwamy element minimalny (siódemkę) w prawym poddrzewie.
15
10 30
4 13 25
7 14 28
Przechodzenie drzewa w głąb i wszerz
Aby wypisać elementy znajdujące się w drzewie mo\
na skorzystać z jednej z dwóch
metod przechodzenia drzewa: w głąb lub wszerz.
Pierwsza z nich to metoda zrealizowana rekurencyjnie. Najpierw zostanie wypisane lewe
poddrzewo, a następnie prawe. Istnieje sześć metod realizacji tego wypisywania. Ró\
niÄ… siÄ™
one kolejnością wykonywanych operacji. Je\
eli wypisywanie to jest realizowane
rekurencyjnie to nale\
y wykonać trzy operacje: wypisać węzeł, wywołać funkcję dla lewego
potomka, wywołać funkcję dla prawego potomka. Kolejność wykonania tych operacji będzie
decydowała o sposobie wypisania danych.
Sześć metod wypisywania (W- wypisz węzeł, P- wywołaj funkcję dla prawego syna, L-
dla lewego syna):
o WLP
o WPL
o LWP
o PWL
o LPW
o PLW
40
Algorytmy i struktury danych
Warto zwrócić uwagę na dwie metody: LWP i PWL. Pierwszy z nich wypisze wartości
rosnąco, drugi malejąco. Jest to zgodne z zasadami, z jakimi wywoływana jest rekurencja
(patrz rekurencja).
Stosując drugą metodę elementy będą wypisywane poziomami. Najpierw zostaną
wypisane elementy z najwy\
szego poziomu (korzeń), potem kolejnego, a na końcu liście
(ostatni poziom). Wykorzystujemy do tego celu kolejkÄ™. Na poczÄ…tku wrzucamy do kolejki
korzeń. Następnie wyciągamy korzeń (wypisujemy go) z kolejki wstawiamy do niej
potomstwo korzenia. Czynność wyciągania węzła z kolejki i wrzucania jego potomstwa
powtarzamy dopóty, dopóki w kolejce coś się znajduje. Jeśli wyciągany element nie posiada
potomstwa to do kolejki nic nie zostanie dodane.
Równowa\
enie drzewa
Często bywa tak, \
e drzewo binarne jest niezrównowa\
one. Drzewo zrównowa\
one
to takie, które ma wypełnione wszystkie poziomy maksymalnie z wyjątkiem być mo\
e
ostatniego poziomu. Tam elementy sÄ… rozlokowane od lewej strony, ale niekoniecznie
wypełniają cały poziom. Przykład takiego drzewa ilustruje poni\
szy rysunek.
15
7 30
4 13 25 34
2 5
Drzewo zrównowa\
one umo\
liwia znacznie szybsze jego przeszukiwanie. W najgorszym
przypadku nasze drzewo mogło by mieć kształt listy. Wtedy, aby przeszukać taką strukturę
nale\
y sprawdzić wszystkie n węzłów drzewa. W najlepszej sytuacji, gdy drzewo będzie
idealnie zrównowa\
one wystarczy sprawdzić węzłów. Nie trudno
îÅ‚log (n +1)Å‚Å‚
2
zauwa\
yć, \
e ró\
nic w ilości porównań jest znaczna. Dla przykładu podam, \
e gdy nasze
drzewo miało by 10 000 elementów to w najgorszym przypadku nale\
ało by sprawdzić
właśnie 10 000 węzłów, a w najlepszym jedynie 14.
Metoda z wykorzystaniem pomocniczej tablicy
To pierwsza z mo\
liwych metod równowa\
enia drzewa binarnego. Najpierw
wykorzystując metodę przechodzenia drzewa w głąb zrzucamy wszystkie elementy drzewa
do tablicy. Co wa\
ne musi to być metoda LWP (elementy muszą być posortowane rosnąco).
Następnie, wykorzystując rekurencję, dodajemy elementy do drzewa. Robimy to w taki
sposób, \
e dodajemy element środkowy tablicy, a następnie wywołujemy funkcje dodaj dla
lewej części tablicy i prawej części.
Nasza funkcja będzie miała dwa argumenty  lewy i prawy indeks tablicy. Pierwsze
wywołanie funkcji nastąpi dla całej tablicy.
41
Algorytmy i struktury danych
Przepis implementacyjny:
wstaw_element(lewy,prawy)
{
jeśli lewy > prawego koniec;
dodajemy element (lewy+prawy)/2 do drzewa;
wywołujemy funkcję dla lewej podtablicy(lewy,(lewy+prawy)/2-1);
wywołujemy funkcję dla prawej podtablicy((lewy+prawy)/2+1,prawy);
}
Przykład: Mamy przykładową tablicę liczb zrzuconych z drzewa i dodajemy je w kolejności:
4, 2 ,1, 3, 6, 5, 7.
1 2 3 4 5 6 7
4
2 6
1 3 5 7
Algorytm DSW
Metoda ta nie wymaga u\
ycia dodatkowej tablicy. Polega ona na obracaniu drzewa w
prawo (lewo) a\
do uzyskania listy, a następnie obracaniu go w lewo (prawo), a\
do
uzyskania drzewa zrównowa\
onego. Podczas tych operacji obowiązują pewne zasady, które
zostały podane przy opisie poni\
szych przykładów.
Przykład 1:
Nasze wyjściowe drzewo niezrównowa\
one wygląda następująco:
10
5 20
3 7
8
Najpierw wykonujemy obroty w prawo (zgodnie ze wskazówkami zegara) a\
do uzyskania
listy. Lewy syn korzenia staje siÄ™ korzeniem, a prawe potomstwo tego syna staje siÄ™ lewym
potomstwem dawnego korzenia, który wędruje w dół. Dokonujemy tego tak długo, a\

korzeń nie będzie miał lewego syna, a następnie to samo robimy dla wszystkich prawych
potomków.
42
Algorytmy i struktury danych
Pierwszy obrót dla korzenia.
5
3 10
7 20
8
Drugi obrót dla korzenia.
3
5
10
7 20
8
Korzeń nie ma ju\
lewego syna, wykonujemy obrót dla pierwszego prawego potomka, który
posiada lewego syna (jest to 10). Prawe poddrzewo węzła, który idzie w górę (siódemki) jest
przyczepiane jako lewe poddrzewo węzła, który idzie w dół (dziesiątki).
3
5
7
10
8 20
Kolejne obroty dla kolejnych prawych potomków, którzy posiadają jeszcze lewe poddrzewa
(dla 10).
3
5
7
8
10
20
43
Algorytmy i struktury danych
Uzyskaliśmy listę, ka\
dy element wskazuje na kolejny. Teraz wykonujemy obroty w lewo
(przeciwnie do wskazówek zegara).
Obroty te wykonujemy wg określonych zasad. Począwszy od korzenia, co drugi
element staje siÄ™ lewym synem swojego prawego potomka. Dodatkowo nale\
y pamiętać, o
ilości wykonywanych obrotów. Najpierw wykonujemy ich tyle, ile wynosi ró\
nica pomiędzy
ilością elementów w naszym drzewie (n), a ilością elementów w najbli\
szym drzewie
pełnym o liczbie elementów mniejszej od naszego drzewa (m). Drzewa pełne to takie, które
mają wszystkie poziomy zapełnione maksymalnie. Ilość węzłów w takim drzewie to 2k - 1,
k " C+
gdzie k to liczba poziomów ( ). Je\
eli nasze drzewo jest drzewem niepełnym o
liczbie węzłów równej n to ilość węzłów w najbli\
szym pełnym drzewie (mającym mniej
2
m = 2ðÅ‚log (n+1)ûÅ‚ -1
węzłów ni\
n) będzie obliczana z wzoru: . A więc najpierw
wykonujemy t = n - m obrotów a następnie wykonujemy ich w ka\
dym cyklu t/2 obrotów
dopóty, dopóki t>0.
Przykładowo, drzewo, które ma 2 poziomy mo\
e maksymalnie mieć 3 węzłów (22 
1). Je\
eli nasze drzewo ma 6 elementów to najbli\
sze pełne drzewo (o liczbie elementów nie
większej od naszego drzewa) ma 3 elementy. Dlatego najpierw wykonujemy 6-3 obrotów
węzłów nadmiarowych (tych, które znajdą się na ostatnim poziomie). W naszym przypadku
obracamy 3, 7 i 10.
5
3 8
7 20
10
Teraz wykonujemy kolejne obroty począwszy od 3/2=1, dla co drugiego węzła począwszy
od korzenia (czyli dla 5).
8
5 20
3 7 10
Na tym kończymy gdy\
ilość obrotów (1/2 = 0) jest równa zero. Nasze drzewo zostało
zrównowa\
one.
44
Algorytmy i struktury danych
Przykład 2:
6
3 8
1 4 7 9
2 5
3
1 6
2 4 8
5 7 9
1
3
2 6
4 8
5 7 9
45
Algorytmy i struktury danych
1
2
3
6
4 8
5 7 9
1
2
3
4
6
8
5
7 9
46
Algorytmy i struktury danych
1
2
3
4
5
6
7
8
9
Teraz następują obroty w lewo.
1
2
3
4
5
6
7
8
9
47
Algorytmy i struktury danych
2
1 4
3 5
6
7
8
9
4
2 6
1 3 5 8
7
9
Gotowe
6
4 8
2 5 7 9
1 3
Tablice haszujÄ…ce
Przechowywanie sporych ilości danych to częste zadanie dla komputerów.
Przeszukiwanie du\
ych zbiorów musi przebiegać sprawnie i szybko. Omówione wcześniej
struktury danych umo\
liwiały sekwencyjne przeszukiwanie danych, jak miało to miejsce w
przypadku list. Aby odnalez
ć na liście dany element nale\
ało przebiec całą jej zawartość po
48
Algorytmy i struktury danych
kolei i porównywać ka\
dą wartość z szukaną. Zło\
oność takiego wyszukiwania wynosiła
O(n). Nieco lepiej było w przypadku drzew binarnych, gdzie wyszukanie elementu miało
zło\
oność O(ln n). Inną metodę składowania danych wykorzystano w przypadku tablic
haszujących. Tutaj klucz (identyfikator rekordu danych) jest jedyną wskazówką informującą
o poło\
eniu danego rekordu w tablicy. Klucz daje nam mo\
liwość bezpośredniego dostania
siÄ™ do danych przez nas szukanych. ZÅ‚o\
oność takiej operacji w najlepszym przypadku jest
rzędu O(1). Miejsce umiejscowienia elementu w tablicy wyznaczamy na podstawie funkcji
haszującej (funkcji mieszającej ang. hash function), której argumentem jest klucz. Klucz ten
mo\
e być ciągiem znaków, liczbą lub rekordem. Wa\
ne jest, aby funkcja haszująca potrafiła
obliczyć na podstawie tego klucza indeks w tablicy, pod którym dany element jest, bądz
te\

ma zostać wstawiony. Idealna funkcja haszująca potrafi przekształcić ka\
dy argument
wejściowy w inny wynik  w inny indeks w tablicy. Zawsze dą\
y siÄ™ do tego, aby funkcja
haszująca była idealna. Dzięki temu nie występują kolizje, a właściwe występują bardzo
rzadko. Z kolizją mamy do czynienia wtedy, gdy więcej ni\
jeden klucz zostały
przekształcone przez funkcję mieszającą na ten sam indeks. Wtedy co najmniej dwa
elementy powinny znajdować się w tym samym miejscu w tablicy. Jest to bardzo często nie
mo\
liwe dlatego istnieją metody rozwiązywania kolizji. Kilka przykładowych zostało
omówiony poni\
ej. Aby móc stworzyć doskonałą funkcję mieszającą tablica powinna
zawierać przynajmniej tyle miejsc ile równych elementów mo\
e wystąpić.
Dla przykładu rozwa\
my problem przechowywania danych osobowych. Ka\
dego
człowieka mo\
na zidentyfikować po numerze PESEL. Wiemy, \
e jest to liczba 11 cyfrowa,
zatem teoretycznie mieści się ona w przedziale od 0 do 1011-1. Jeśli chcielibyśmy
przechowywać dane osób z danego obszaru  powiedzmy 105 elementów, to od razu
wiadomo, \
e elementów do zapamiętania będzie znacznie mniej ni\
1011. Jednak, aby nasza
funkcja mieszają był idealna to tablica powinna mieścić 1011 elementów. Przy zało\
eniu, \
e
wykorzystamy zaledwie znikomy procent komórek takie rozwiązanie jest złe. Mo\
liwe jest
takie dobranie funkcji haszującej, która co prawda nie wyeliminuje kolizji, jednak znacząco
pozwoli ograniczyć rozmiar naszej tablicy. Dobranie rozmiaru tablicy do ilości elementów
jakie będziemy w niej przechowywać zale\
y od wielu czynników. Powiedzmy, \
e zazwyczaj
ilość dostępnych komórek powinna być trzy razy większa od ilości elementów, które
będziemy przechowywać. Dla naszego przykładu była by to tablica 3* 105.
Jak wyznaczyć funkcję haszującą, która pozwoli przekształcić argument wejściowy w
indeks w tablicy. Metoda jest kilka Najpopularniejsze z nich zostaną omówione poni\
ej.
Funkcje haszujÄ…ce  metody ich wyznaczania
Pierwsza metoda wyznaczania funkcji haszujÄ…cej polega na podzieleniu modulo
klucza przez liczbę D będącą rozmiarem tablicy i wzięciu reszty z tego dzielenia. Niestety
często zdarza się, \
e w takim przypadku wystąpi znaczna ilość kolizji. Mo\
na ten efekt
ograniczyć dobierając odpowiednio liczbę D. Najlepiej, jeśli będzie to liczba pierwsza. Mo\
e
to nie być liczba pierwsza, jednak powinna być tak dobrana, aby jej czynniki pierwsze
(uzyskane po rozkładzie na czynniki pierwsze) był du\
e.
Druga metoda polega na składaniu elementów klucza. Najpierw klucz dzieli się na
klika części, a następnie łączy się te elementy poddając je ró\
nego rodzaju operacjom.
Przykładowo mając numer telefonu 506-123-678 mo\
emy podzielić go na trzy części 506, 123
i 678 i zsumować te elementy uzyskując 1307. Teraz mo\
emy otrzymaną liczbę podzielić
modulo przez rozmiar tablicy D i wziąć resztę z dzielenia jako indeks. Podział klucza
wejściowego mo\
emy dokonywać na ró\
ny sposób, składając go póz
niej tak\
e ró\
nymi
metodami. Innym sposobem składania klucza polega na podzieleniu go na kilka części. W
naszym przypadku pozostaniemy przy 506, 123, 678. Następnie Parzyste części klucza
zapisujemy od końca. 506, 321, 678. W kolejnym kroku sumujemy te elementy i uzyskujemy
49
Algorytmy i struktury danych
1505, które dzielimy modulo przez rozmiar D i jako indeks bierzemy resztę z dzielenia.
Warto zaznaczyć, \
e aby przyspieszyć operacje przetwarzania klucza wszystkie działania
wykonujemy na bitach wykorzystując podstawowe operacje na bitach. Dla ciągów znaków
mo\
na wykorzystać operacje składania znaków poprze operacje logiczną OR (np.  n OR  a
OR  z OR  w OR  a ). Wadą tego rozwiązania jest wynik, który zawsze mieści się w
przedziale 0-127. Mo\
na tak\
e wykonywać operacje logiczną na zbiorach znaków.
Przykładowo ciąg nazwa mo\
na przekształcić:  na XOR  zw .
Rozwiązywanie kolizji metodą łańcuchową
To najprostsza z metod rozwiÄ…zywania kolizji. Tablica przechowujÄ…ca dane tu
przechowuje wskaz
niki do list. Problem rozwiązano w taki sposób, \
e elementy, które
funkcja haszująca przydzieliła pod ten sam indeks znajdują się na liście, która jest
 przyczepiona pod tym indeksem. W ten sposób listy wydłu\
ajÄ… siÄ™ wraz ze wzrostem
ilości kolizji na danej pozycji. Jeśli ilość kolizji spowoduje znaczny wzrost długości list to
efektywność takiego algorytmu zmniejszy się. Problem ten mo\
na zminimalizować stosują
listy posortowane (patrz punkt listy). Inną wadą tego rozwiązania jest dodatkowa pamięć
potrzebna na przechowywanie wskaz
ników do listy oraz wskaz
ników do następnego
elementu. Przy n elementach wskaz
ników tych będzie n + D.
0 NULL
elem elem
1 NULL
2
NULL
elem
3
NULL
elem elem
4
NULL
5
NULL
elem
Adresowanie otwarte
Kiedy funkcja haszująca zwróci indeks ju\
zajęty przez inny element powstaje kolizja.
Jedną z metod rozwiązywania tego typu problemów jest adresowanie otwarte. Je\
eli
zwrócony indeks jest ju\
zajęty znajduje się kolejny wolny indeks w tablicy. Istnieją ró\
ne
metody wyszukiwania kolejnych wolnych indeksów. Tablice przeszukuje się dopóty, dopóki
nie znajdzie się wolnej komórki lub trafi się do komórki w tablicy ju\
sprawdzonej albo
tablica będzie pełna.
NajprostszÄ… metodÄ… adresowania otwartego jest adresowanie liniowe. Metoda ta
polega na wstawianiu elementu w pierwszÄ… wolnÄ… pozycjÄ™ tablicy (po wyznaczonej przez
funkcjÄ™ h), je\
eli pozycja wyznaczona przez funkcję haszującą h(klucz) jest zajęta. Najpierw
wyznaczamy indeks zgodnie z funkcjÄ… haszujÄ…cÄ…, a je\
eli jest on zajęty to sekwencyjnie
przeszukujemy kolejne komórki, a\
trafimy na wolne miejsce. Nale\
y pamiętać, aby
zabezpieczyć się przed wyjściem poza obszar pamięci przydzielony dla tablicy. W tym celu
wystarczy wartość wyznaczonego indeksu dzielić modulo przez rozmiar tablicy D.
indeks = [h(klucz) + krok] mod D, gdzie krok e" 0
50
Algorytmy i struktury danych
Metoda ta rozwiÄ…zuje problem kolizji, jednak mo\
e powodować częste grupowanie się
zbiorów elementów. Ma to niekorzystne znaczenie podczas wyszukiwania elementów 
uniemo\
liwia szybkie zakończenie tej operacji.
Kolejna odmiana adresowania otwartego to adresowanie kwadratowe. W tym
przypadku indeks kolejnej komórki do której nale\
y przejść w przypadku kolizji wyznacza
funkcja kwadratowa.
indeks = [h(klucz) + c * krok + c * krok2] mod D
1 2
c ,c to liczby dobrane tak, aby zapobiec zapętleniu się funkcji. Najlepiej, gdy są to liczby
1 2
pierwsze. RozwiÄ…zanie to zapobiega powstawaniu du\
ych zbiorów liczb z sąsiednich
indeksów.
Ostatnia odmiana to adresowanie podwójne. W tym przypadku indeks początkowy
wyznacza funkcja haszujÄ…ca, a w przypadku kolizji kolejny indeks jest wyznaczany na
podstawie drugiej funkcji, której argumentem jest tak\
e klucz.
indeks = [h(klucz) + krok * f(klucz)] mod D
Druga funkcja jest wyznaczana przy pomocy tych samych metod co pierwsza. Mo\
na
skorzystać z podziału modulo. Dzielimy klucz tak\
e przez liczbÄ™ pierwszÄ…, jednak o
mniejszej wartości ni\
w funkcji h.
Poszukiwanie elementu w tablicy haszujÄ…cej polega na wyznaczeniu indeksu
szukanego elementu na podstawie jego klucza i sprawdzeniu czy dany element tam jest. Jeśli
nie to zgodnie z ideÄ… adresowania otwartego mo\
e on znajdować się w kolejnych
komórkach. Sprawdzamy kolejne komórki wyznaczone na podstawie przyjętej metody
(liniowej, kwadratowej, podwójnej). Poszukiwanie kontynuujemy dopóty, dopóki nie
natrafimy na komórkę pustą lub trafimy w miejsce ju\
sprawdzone.
Usuwanie elementu wykonujemy w dwóch etapach: najpierw odnajdujemy dany
element, a następnie usuwamy go z tablicy. Tu pojawia się jednak pewien problem. Nie
mo\
na tak po prostu usunąć elementu (np. wyzerować komórkę), gdy\
mo\
e się zdarzyć
tak, \
e podczas kolejnego wyszukiwania nie zadziała opisany algorytm.
Przykład: Mamy tablice haszującą. Nasza funkcja haszująca będzie wyznaczała indeks
biorąc resztę z dzielenia klucza przez 11. Wypełniamy ją kolejno liczbami: 14, 15, 26 (kolizja z
15  wstawiamy na kolejnej pozycji), 37 (kolizja z 15 i 26  wstawiamy na pierwszej wolnej
pozycji), 18, 30.
&
3 14
4 15
5 26
6 37
7 18
8 30
9
10
&
51
Algorytmy i struktury danych
Teraz usuwamy liczbę 26  wymazując tylko komórkę.
&
3 14
4 15
5
6 37
7 18
8 30
9
10
&
W następnym kroku szukamy liczby 37. Dzielimy ją modulo przez 11 i otrzymujemy resztę
4. ZaglÄ…damy pod indeks 4  nie ma jej tam. Poniewa\
stosujemy adresowanie liniowe
zaglądamy do następnej komórki pod indeks 5. Tam tak\
e nie ma liczby 37. W kolejnej
komórce tablicy nie ma ju\
nic (wymazaliśmy stamtąd 26). Zgodnie z ideą przeszukiwania
opisanÄ… powy\
ej kończymy stwierdzając, \
e liczby 37 nie ma w tablicy. Jak siÄ™ jednak
okazuje wniosek ten jest nieprawdziwy. Tu ujawnia siÄ™ problem zwiÄ…zany z usuwaniem
danych. Nie mo\
na po prostu  wymazać komórki. Nale\
y zaznaczyć, \
e komórka ta była
zajmowana. Oznaczać to będzie, \
e podczas przeszukiwania będziemy ją traktować tak
jakby coś tam było, a podczas wstawiania uznamy, \
e jest ona pusta i mo\
na w niej umieścić
element. Spróbujmy teraz jeszcze raz usunąć liczbę 26, ale tym razem wstawimy do tej
komórki X  jako symbol wcześniejszego wypełnienia komórki.
&
3 14
4 15
5 X
6 37
7 18
8 30
9
10
&
Teraz szukając liczby 37 w 2 kroku trafiamy do komórki o indeksie 5, stwierdzamy, \
e to nie
jest liczba 37 i idziemy dalej  nie przerywając poszukiwań. Doprowadzi nas to w kolejnym
kroku do komórki o indeksie 6, gdzie znajduje się szukany element.
Rozwa\
my teraz wstawianie liczby 25 do tablicy. Funkcja haszujÄ…ca zwraca nam
indeks 3. Jest on jednak zajęty, więc próbujemy wstawić liczbę pod 4  to tak\
e jest
niemo\
liwe. Pod indeksem 5 udaje nam się wstawić dany element. Pomimo, \
e komórka nie
jest pusta (zawiera X) to podczas wstawiania traktujemy ten znak jakby komórka nie
zawierała elementu.
52
Algorytmy i struktury danych
&
3 14
4 15
5 25
6 37
7 18
8 30
9
10
&
Teoria grafów
Podstawowe definicje
Graf to zbiór wierzchołków i krawędzi, które łączą te wierzchołki. Jest to struktura o
wiele bardziej elastyczna od drzew czy list. Nie istniejÄ… tu tak precyzyjne restrykcje, co do
połączeń poszczególnych węzłów. Grafy mo\
na klasyfikować ze względu na wiele
własności. Pierwsza z nich dotyczy kierunku krawędzi. Mo\
emy wyró\
nić grafy skierowane
i niekierowane. W pierwszym przypadku krawędzie mają określony kierunek, w którym
mo\
na się poruszać po danej krawędzi. W drugim przypadku ka\
da z krawędzi umo\
liwia
ruch w obu kierunkach.
Graf nieskierowany Graf skierowany
Inna klasyfikacja grafów to podział grafów na ogólne i proste. Pierwsza grupa cechuje się
tym, \
e uwzględnia pewne mo\
liwości w tworzeniu grafów, które nie występują w grafach
prostych. Pierwsza z tych mo\
liwości to istnienie krawędzi równoległych  czyli
przynajmniej dwóch krawędzi łączących te same węzły. W grafie skierowanym dwie
krawędzi łączące te same wierzchołki, ale mające przeciwne kierunki nie są krawędziami
równoległymi.
53
Algorytmy i struktury danych
krawędzie równoległa to nie są krawędzie
równoległa
Graf nieskierowany Graf skierowany
DrugÄ… z mo\
liwości jest istnienie pętli własnych. Jest to krawędz
Å‚Ä…czÄ…ca ze sobÄ… ten sam
wierzchołek.
pętla własna
Istnieją grafy, w których nie występują \
adne krawędzie  o takich grafach mówimy
grafy puste. Mo\
liwa jest tak\
e sytuacja, w której graf nie będzie miał nie tylko krawędzi, ale
tak\
e węzłów. Wtedy nazywać go będziemy grafem zerowym.
Graf pusty
Skoro istniejÄ… grafy puste, to tak\
e mo\
na mówić o istnieniu grafów pełnych. Z grafem takim
będziemy mieć do czynienia wtedy, gdy ilość krawędzi w takim grafie będzie maksymalna.
Poni\
szy wzór pozwala obliczyć maksymalną ilość krawędzi w grafie o n wierzchołkach.
n
ëÅ‚ öÅ‚ -1)
n(n
ìÅ‚ ÷Å‚ =
ìÅ‚
2÷Å‚ 2
íÅ‚ Å‚Å‚
Grafy pełne
Z wierzchołkami grafów tak\
e jest związanych kilka pojęć. Mo\
na mówić o
wierzchołku izolowanym  czyli takim, który nie jest połączony krawędzią z \
adnym innym
wierzchołkiem tego grafu.
54
Algorytmy i struktury danych
wierzchołek
izolowany
Stopień wierzchołka, czyli ilość sąsiadów, który posiada dany wierzchołek. W przypadku
grafów nieskierowanych podaje się ilość krawędzie powiązanych z wierzchołkiem. W
grafach skierowanych wyró\
niamy stopień wejściowy i wyjściowy wierzchołka. Pierwszy
określa ilość krawędzi wchodzących do wierzchołka, a drugi  wychodzących z wierzchołka.
Stopień wychodzący
wierzchołka wynosi 1,
Stopień
a wchodzÄ…cy 2,
wierzchołka
natomiast stopień
wynosi 3.
ogólny 3
Graf skierowany
Graf nieskierowany
Izomorfizm to sytuacja, w której dwa grafy mają taką samą liczbę wierzchołków tych
samych stopni oraz taką samą liczbę krawędzie mających te same wagi. Innymi słowy dwa
grafy mogą być inaczej rozrysowane, ich wierzchołki mogą nazywać się inaczej, jednak w
obu grafach będzie ta sama liczba wierzchołków o danym stopniu i taka sama ilość krawędzi
o danej wadze. Przykładowo, jeśli w grafie G są dwa wierzchołki o stopniu 3, jeden o stopniu
5 i trzy o stopniu 2 to w grafie G musi istnieć dokładnie taki sam układ. Poni\
ej
przedstawiono dwie pary grafów. Pierwsza to grafy izomorficzne, natomiast grafy w drugiej
parze nie sÄ… izomorficzne.
graf G graf G
55
Algorytmy i struktury danych
Cykl grafu to droga przejścia z wierzchołka do tego samego wierzchołka. Krawędzie,
którymi się poruszamy tworzą cykl.
cykl
Spójność grafu to cecha, dzięki której z dowolnego wierzchołka w grafie idzie dojść do
wszystkich pozostałych wierzchołków w tym grafie. Graf taki nazywamy grafem spójnym.
Grafy niespójne zawsze dzielą się na składowe grafy spójne.
spójne składowe
Graf spójny Graf niespójny
Podgrafem nazywamy graf będący częścią innego grafu.
Graf Podgraf grafu po lewej stronie
Je\
eli dany zbiór wierzchołków da się podzielić na dwa podzbiory i wierzchołki jednego
podzbioru są połączone tylko z wierzchołkami z drugiego podzbioru to mamy do czynienia
z grafem dwudzielnym. Zastosowań takiego rozwiązania jest wiele, np. jeden podzbiór to
mogą być zadania do wykonania, a drugi to procesory. Ka\
dy z procesorów mo\
e
wykonywać określone zadania. Graf taki mo\
e m.in. posłu\
yć do obliczania maksymalnych
skojarzeń (zostanie to omówione póz
niej). Poni\
ej znajdują się przykłady grafów
dwudzielnych.
56
Algorytmy i struktury danych
Brak połączeń
wewnÄ…trz danego
podzbioru.
6
1 2 1 5
3 4
4
2
6
3
5
Te grafy są równowa\
ne
Graf z wagami to graf, w którym ka\
da z krawędzi ma odpowiednią wagę (priorytet).
Przykładowo, je\
eli graf przedstawia miasta połączone ze sobą, to wagą krawędzi mo\
e być
długość drogi łączącej te dwa punkty.
2 3
4 9 3 4
1 9
7 9
3 1
3 6
Graf nieskierowany Graf skierowany
z wagami z wagami
Nale\
y zauwa\
yć równie\
, \
e drzewa to te\
grafy, który nie mają cykli. Mówiąc drzewo nie
mam na myśli drzewa binarnego, ale zwykłe. Spójne drzewo posiada dokładnie n-1
krawędzi, gdzie n to ilość wierzchołków.
57
Algorytmy i struktury danych
a
e
f
c
b
g
d
Oba drzewa sÄ…
równowa\
ne  sÄ… to grafy
c
e d b a
f
g
Reprezentacja grafów w komputerze
Pierwsza z metod reprezentacji grafu w komputerze wykorzystuje listy i nazywana
jest listÄ… sÄ…siedztwa. W reprezentacji tej ka\
dy z wierzchołków ma przydzielony numer. W
pamięci komputera tworzymy tablice o rozmiarze równym ilości wierzchołków. Ka\
dy i-ty
element tej tablicy wskazuje na listę, na której przechowujemy numery wierzchołków z
którymi połączony jest wierzchołek i. Ten sposób przechowywania grafu w pamięci jest
dobry dla grafów o małej liczbie krawędzi, gdy\
wtedy listy będą stosunkowo krótkie. W
przypadku grafów nieskierowanych na listach wystąpią powtórzenia związane z
dwukierunkowością ka\
dej z krawędzi. Poni\
ej znajduje siÄ™ graf (po lewej) oraz jego
reprezentacja z wykorzystaniem list (po prawej).
0 3 1 2
0 0 3
1
c a
5
2 3 0
1
g b
2 0 2 1 4
3
e
4 4 3
f d
4
3 4
5
Druga metoda reprezentacji grafu w komputerze wykorzystuje macierz określaną
macierzą sąsiedztwa. Dla grafu o n wierzchołkach tworzymy macierz n na n i wpisujemy
jedynki w miejsca, gdzie występuje połączenie. Wypełniania macierzy mo\
emy dokonywać
wierszami (ewentualnie kolumnami). W ka\
dym i-tym wierszu wstawiamy jedynkÄ™ w j-tej
kolumnie jeśli i-ty wierzchołek ma połączenie z j-tym wierzchołkiem. Oczywiście w
przypadku grafów nieskierowanych macierz ta będzie symetryczna. Poni\
ej znajduje siÄ™
przykład macierzy sąsiedztwa dla grafu przedstawionego powy\
ej.
58
Algorytmy i struktury danych
0 1 2 3 4 5
0 0 1 1 1 0 0
1 1 0 0 1 0 0
2 1 0 0 1 0 0
3 1 1 1 0 1 0
4 0 0 0 1 0 1
5 0 0 0 0 1 0
Rozmiar macierzy zale\
y tutaj od ilości krawędzi. Przy grafach gęstych zu\
ywamy mniej
pamięci ni\
w przypadku metody list sąsiedztwa. Aby zapamiętać informację o jednej
krawędzi wystarczy nam jeden bit pamięci. Dlatego podczas implementacji tej metody
reprezentacji grafu warto skorzystać (zwłaszcza przy du\
ych grafach) z operacji na bitach.
Przykładowo w 8-elementowej tablicy unsigned char (typ zajmujący w języku C 1 bajt)
mo\
na przechowywać macierz sąsiedztwa grafu mającego 8 wierzchołków.
Trzecia metoda reprezentacji grafu wykorzystuje macierzÄ… incydencji. Jest to macierz
o wymiarach n (wierszy) na m (kolumn), gdzie n to ilość wierzchołków w grafie, a m  ilość
krawędzi. W macierzy takiej dla i-tego wiersza (wierzchołka) wstawiamy jedynkę w tej
kolumnie, która reprezentuje krawędz
powiązaną z i-tym wierzchołkiem. Ka\
da z kolumn
zawiera jedynie dwie jedynki, gdy\
jedna krawędz
mo\
e łączyć ze sobą jedynie dwa
wierzchołki. Przykład macierzy incydencji dla przedstawionego powy\
ej grafu został
zaprezentowany poni\
ej.
a b c d e f g
0 1 1 1 0 0 0 0
1 0 0 1 0 1 0 0
2 1 0 0 1 0 0 0
3 0 1 0 1 1 1 0
4 0 0 0 0 0 1 1
5 0 0 0 0 0 0 1
Przechodzenie grafu w głąb, wyznaczanie spójnych składowych
Pierwsza z metod nazywa się w głąb (DFS ang. depth-first search). Podczas
przechodzenia grafu tą metodą rozpoczynamy od dowolnego wierzchołka i odchodzimy od
niego najdalej jak się da, a następnie wracamy z powrotem. W kolejnym kroku wybieramy
następny, jeszcze nieodwiedzony wierzchołek i znów idziemy najdalej jak to mo\
liwe.
WyglÄ…da to podobnie jak w przypadku drzew, ale nale\
y zaznaczać swoją obecność
w wierzchołku, w którym się jest, aby nie trafić tam ponownie, co zapobiegnie zapętleniu.
Mo\
na to rozwiązać poprzez wprowadzenie dodatkowej tablicy o rozmiarze równym ilości
wierzchołków. Zero w takiej tablicy oznacza, \
e nie byliśmy tam jeszcze, jeden-
odwiedziliśmy, a dwa- przetworzyliśmy. Przetworzenie i-tego wierzchołka oznacza stan, w
którym wszyscy sąsiedzi tego wierzchołka zostali ju\
odwiedzeni. W momencie wejścia do
wierzchołka zaznaczamy jego odwiedzenie. Do przechodzenie w głąb równie\

wykorzystujemy rekurencję, wywołując funkcję dla wszystkich sąsiadów i-tego
(nieodwiedzonego jeszcze) wierzchołka. W momencie gdy powrócimy do i-tego wierzchołka
i nie da siÄ™ nigdzie ju\
iść, wierzchołek taki uznajemy za przetworzony. Przykład
przechodzenia grafu w głąb pokazano poni\
ej. Przy ka\
dym z wierzchołków podano
kolejność odwiedzin oraz (po znaku  / ) kolejność przetworzenia.
59
Algorytmy i struktury danych
1/6 f 6/1
a
b
2/5
e
5/2 3/4
c
d
4/3
Metoda przechodzenia w głąb umo\
liwia obliczenie ilości spójnych składowych w
grafie. Wywołując funkcję odwiedzin dla dowolnego wierzchołka startowego, odwiedzimy
tylko te wierzchołki, do których da się dotrzeć. Utworzą one pierwszą spójną składową. Jeśli
ilość wierzchołków w tej spójnej składowej jest mniejsza od całkowitej liczby wierzchołków,
to graf jest niespójny i posiada więcej spójnych składowych.
Przechodzenie grafu wszerz
Druga metoda nazywa siÄ™ wszerz (BFS ang. breadth-first search). Podczas
przechodzenia grafu tÄ… metodÄ… rozpoczynamy tak\
e od dowolnego, i-tego wierzchołka i
odwiedzamy najpierw wszystkie wierzchołki le\
Ä…ce najbli\
ej i-tego wierzchołka, czyli te w
odległości jednej krawędzi. Następnie odwiedzamy te le\
ące w odległości dwóch krawędzi
itd.
Podobnie jak w przypadku drzew wykorzystujemy do tego celu kolejkÄ™. Wrzucamy
i-ty wierzchołek (niewrzucony jeszcze) do kolejki i jeśli coś jest w kolejce to zdejmujemy
element i wrzucamy wszystkich sąsiadów tego zdejmowanego wierzchołka (oczywiście
tylko tych, których jeszcze nie wrzucaliśmy). Pamiętać nale\
y o zaznaczaniu swojej
obecności w wierzchołku (wrzucenia wierzchołka do kolejki).
Przechodząc graf wszerz odwiedzimy tylko te wierzchołki, do których mo\
emy dojść
z wierzchołka startowego. Umo\
liwi nam to sprawdzenie spójności. Je\
eli ilość
odwiedzonych wierzchołków jest mniejsza od ilości wierzchołków w drzewie to graf jest
niespójny. Poni\
ej narysowano przykładowy graf. Przy ka\
dym z wierzchołków napisano
kolejność jego wypisania (zdjęcia z kolejki).
1 f 6
a
b
2
e
4 3
c
d
5
Sortowanie topologiczne
W grafach nie majÄ…cych cykli mo\
emy odwiedzać węzły w takiej kolejności, aby dla i-
tego węzła wszyscy jego najbli\
si sÄ…siedzi zostali odwiedzeni, zanim on sam zostanie
odwiedzony. W takim przypadku węzły będą odwiedzane zgodnie z kolejnością
topologicznÄ…. Algorytm umo\
liwiajÄ…cy takie odwiedzanie nazywa siÄ™ sortowaniem
60
Algorytmy i struktury danych
topologicznym. Grafy umo\
liwiające sortowanie topologiczne węzłów określane są mianem
grafów zale\
ności.
Przykład wykorzystania grafów zale\
ności i sortowania topologicznego
przedstawiono na poni\
szym rysunku (poni\
sze dwa grafy sÄ… izomorficzne). Problem
polega na znalezieniu kolejności, w jakiej nale\
y się rano ubierać. Aby się tego dowiedzieć
nale\
y przejść poni\
szy graf w głąb, a elementy przetworzone wypisać w kolejności
malejących czasów przetworzenia. Mo\
na wrzucać je na stos, a następnie je stamtąd zdjąć. W
ka\
dym z węzłów podano kolejność odwiedzenia oraz (po znaku  / ) kolejność
przetworzenia. Rozpoczynamy od  slipów :&.
skarpety 8/8
slipy 1/7
buty 5/5
spodnie 2/6
koszula 6/4
pasek 3/2
krawat 7/3
marynarka 4/1
zegarek 9/9
slipy spodnie pasek buty koszula krawat marynarka skarpety
1/7 2/6 3/2 5/5 6/4 7/3 4/1 8/8
zegarek
9/9
Wierzchołki przetworzono w następującej kolejności: marynarka, pasek, krawat, koszula,
buty, spodnie, slipy, skarpety, zegarek. Zatem aby udało nam się ubrać, musimy zakładać te
rzeczy w odwrotnej kolejności: zegarek, skarpety, slipy, spodnie, buty, koszule, krawat,
pasek, marynarka.
Wyznaczanie silnych spójnych składowych w grafie skierowanym
Jak ju\
wcześniej wspomniano grafy skierowane to takie grafy, w których wa\
ny jest
kierunek ście\
ki łączącej dwa węzły. Efektem tego są sytuacje, w których mo\
na przejść z
punktu A do B, ale nie mo\
na z B do A. SytuacjÄ™ mo\
na przyrównać do dróg w mieście.
Niektóre są dwukierunkowe, ale są te\
takie, którymi mo\
na poruszać się tylko w jednym
kierunku. Przykładowy schemat grafu skierowanego przedstawiony jest poni\
ej.
61
Algorytmy i struktury danych
Krawędz
Krawędz

jednokierunkowa dwukierunkowa, ale
(tylko z A do B) nie równoległa.
A B C D
E F G H
Spójność to sytuacja, w której z dowolnego wierzchołka grafu mo\
emy dojść do
ka\
dego innego wierzchołka (istnieje droga do wszystkich pozostałych wierzchołków). W
przypadku grafów skierowanych sytuacja jest nieco bardziej skomplikowana. Tutaj mamy
do czynienia z dwoma rodzajami spójności: słabą i silną.
Sprawdzanie spójności słabej (szukanie spójnych składowych) odbywa się
identycznie jak w przypadku grafu nie skierowanego. Najpierw graf skierowany
 zamieniamy na nie skierowany i szukamy spójnych składowych. Innymi słowy ka\
dÄ…
krawędz
traktujemy jako dwukierunkowÄ…. Przedstawiony powy\
ej graf będzie spójnych
gdy\
ma tylko jedną spójną składową.
W przypadku spójności silnej wa\
ny jest ju\
kierunek krawędzi. Definicja tej
spójności jest taka: graf skierowany spójny to taki, w którym z ka\
dego wierzchołka idzie
dojść do wszystkich pozostałych wierzchołków w grafie. Spróbujmy intuicyjnie znalez
ć silne
spójne składowe w naszym przykładowym grafie. Rozpoczynając od wierzchołka A
(mo\
liwy jest dowolny wierzchołek) stwierdzamy, \
e bez problemów mo\
na poruszać się
pomiędzy A, B i E. Do wierzchołków C, D, F, G oraz H tak\
e dotrzemy jednak z tych
wierzchołków nie mo\
na powrócić ju\
do A, B lub E. Zatem wierzchołki A, B, oraz E tworzą
pierwszą silną spójną składową tego grafu. Kolejne silne spójne składowe zakreślono
kolorowymi kreskami.
A B C D
E F G H
W przypadku tak małego grafu nie było trudno odszukać silne spójne składowe. Jednak
gdybyśmy mieli to zrobić w du\
o większym grafie pojawiłyby się problemy.
Aby znalez
ć silne spójne składowe w dowolnym grafie nale\
y zastosować algorytm.,
którego kolejne kroki podano poni\
ej. KorzystajÄ…c z tego algorytmu znajdziemy jeszcze raz
silne spójne składowe w naszym grafie.
62
Algorytmy i struktury danych
Najpierw przechodzimy graf w głąb i zapisujemy czasy przetworzenia
poszczególnych wierzchołków. Na poni\
szym rysunku przy ka\
dym z wierzchołków
napisano numery kolejnych kroków przechodzenia grafu. Na kolorowym tle podano krok, w
którym wierzchołek został przetworzony. Zaczynamy od dowolnego wierzchołka (np. C).
14/15 12/17 1/6/11 2/5
A B C D
E F G H
13/16 8/9 7/10 3/4
Przeszliśmy graf w głąb. Rozpoczęliśmy od C i poruszaliśmy się tak długo, a\
powróciliśmy do C i ju\

nigdzie nie szło iść. następnie wzięliśmy kolejny nieodwiedzony wierzchołek (B) i przechodziliśmy graf
dalej. W ten sposób mam spisane czasy przetworzeń poszczególnych wierzchołków.
Kolejny krok naszego przepisu to transpozycja grafu. Polega to za zamienieniu
kierunków krawędzi. Innymi słowy, je\
eli krawędz
prowadziła z A do B to teraz
poprowadzi z B do A. Poni\
ej przedstawiono nasz graf po transpozycji.
14/15 12/17 1/6/11 2/5
A B C D
E F G H
13/16 8/9 7/10 3/4
Jednym ze sposobów przechowywanie grafu w pamięci była macierz sąsiedztwa. Dla
pierwotnego naszego grafu (tego przed transpozycją) wyglądała ona następująco.
A B C D E F G H
A 0 1 0 0 0 0 0 0
B 0 0 1 0 1 1 0 0
C 0 0 0 1 0 0 1 0
D 0 0 1 0 0 0 0 1
E 1 0 0 0 0 1 0 0
F 0 0 0 0 0 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 0 1
Natomiast macierz sÄ…siedztwa grafu transponowanego to po prostu transponowana macierz
grafu pierwotnego. Transpozycja macierzy polega na zamianie wiersze z kolumnami. Po
transponowaniu wyglÄ…da tak:
A B C D E F G H
A 0 0 0 0 1 0 0 0
B 1 0 0 0 0 0 0 0
C 0 1 0 1 0 0 0 0
D 0 0 1 0 0 0 0 0
E 0 1 0 0 0 0 0 0
F 0 1 0 0 1 0 1 0
G 0 0 1 0 0 1 0 0
H 0 0 0 1 0 0 1 1
63
Algorytmy i struktury danych
Ostatni krok naszego przepisu to znów przejście naszego transponowanego grafu w głąb, ale
tutaj wa\
na jest kolejność wierzchołków od których zaczynamy. Zawsze przechodzenie
odbywa się według malejących czasów przetworzenia z poprzedniego przejścia.
Rozpoczynamy od wierzchołka, który przetworzyliśmy jako ostatni, czyli od B. Gdy ju\
nie
da się iść dalej, rozpoczynamy przejście od kolejnego wierzchołka, który jeszcze nie
odwiedziliśmy. Nale\
y pamiętać, \
e wybieramy wierzchołek nieodwiedzony o największym
czasie przetworzenia.
2/5 1/6 7/10 8/9
A B C D
E F G H
3/4 12/13 11/14 15/16
Poszczególne kroki przejść rozpisano w ró\
nym kolorze. Najpierw znalez
liśmy ABE, potem
CD, EG i na końcu H. Zatem graf ten ma cztery silne spójne składowe- zgodnie z tym, co
rozrysowaliśmy wcześniej intuicyjnie.
TrochÄ™ o Å‚Ä…czeniu w zbiory
Mając daną pewną ilość elementów mo\
na je połączyć w zbiory. Przykładowo
uczniów jednej klasy wrzucamy do zbioru IA, a drugiej do zbioru IB. Oczywiście musi
istnieć pewien łącznik, dzięki któremu ka\
dy będzie mógł stwierdzić do którego zbioru
nale\
y. Mo\
na przykładowo uczniom klasy IA powiedzieć, \
e ich przewodniczÄ…cym jest
uczeń X, a uczniom IB, \
e przewodniczącym jest uczeń Y. W ten sposób ka\
da grupa będzie
znała swojego lidera, po którym będzie kojarzona z danym zbiorem. Podobnie mo\
na zrobić
z dowolnymi elementami. Przykładowo, mamy ciąg liczby od 0 do 6. Ka\
da z nich tworzy
jednoelementowy zbiór. My chcemy te liczby połączyć w większe zbiory.
0 5
3
1
2 6
4
Powiedzmy, \
e chcemy na początek połączyć 0 i 5 w jeden zbiór. Wybieramy lidera dla tego
zbioru. Niech będzie to 5. Lidera mo\
na wybierać według ró\
nych zasad, w zale\
ności od
rodzaju elementów jakie grupujemy. Przykładowo, dla cyfr mo\
e to być największa liczba ze
zbioru.
64
Algorytmy i struktury danych
0 5
1
2 3
4
6
Jednym ze sposobów implementacji łączenia w zbiory mo\
e być zastosowanie pomocniczej
tablicy. Jest to bardzo dobra metoda w przypadku Å‚Ä…czenia liczb naturalnych. Tworzymy
tablicę o takim zakresie, jaki obejmują nasze liczby. U nas będzie to tablica od zera do
sześciu. Pod odpowiednim indeksem danej liczby będziemy przechowywali informację o
liderze zbioru, do którego nale\
y dana liczba. Nasz tablica na początku (gdy będziemy mieć
zbiory jednoelementowe) wyglądałaby następująco:
0 1 2 3 4 5 6
0 1 2 3 4 5 6
Teraz wykonajmy kilka przykładowych operacji łączenia zbiorów.
1) Połączmy 0 z 5, a jako lidera wybierzmy największą liczbę  czyli 5.
0 1 2 3 4 5 6
5 1 2 3 4 5 6
2) W kolejnym kroku połączymy 2 z 3  liderem zostaje 3.
0 1 2 3 4 5 6
5 1 3 3 4 5 6
3) Teraz połączymy zbiór {0,5} ze zbiorem jednoelementowym {6}  lider to 6.
0 1 2 3 4 5 6
6 1 3 3 4 6 6
4) Kolejna operacja to połączenie zbioru {2,3} z {4}  liderem jest 4
0 1 2 3 4 5 6
6 1 4 4 4 6 6
Po wykonaniu powy\
szych operacji otrzymaliśmy zbiory, których graficzną postać
przedstawiono poni\
ej.
65
Algorytmy i struktury danych
0 5
6
1
2
3
4
W tej metodzie implementacji, aby dowiedzieć się do jakiego zbioru nale\
y i-ty element
wystarczy sprawdzić co znajduje się pod i-tym indeksem w tablicy.
Innym sposobem implementacji zbiorów jest zastosowanie list. Elementy z danego
zbioru tworzą listy, w których ka\
dy węzeł oprócz wskaz
nika następny wskazującego na
następny obiekt zawiera tak\
e wskaz
nik lider wskazujÄ…cy na lidera zbioru. Przedstawiony
powy\
ej przykład zbiorów wyglądał by następująco.
6 0 5
4 2 3
1
Podczas operacji łączenia zbiorów A i B nale\
y wskaz
nik następny ze zbioru A, który
wskazywał na Null skierować na początek zbioru B. Nale\
y tak\
e wszystkie wskaz
niki lider
w zbiorze B skierować na lidera w zbiorze A. Mo\
na tak\
e ustalić nowego wspólnego lidera
dla nowo powstałego zbioru i ustawić wszystkie wskaz
niki lider na nowego lidera. Dla
przykładu połączymy zbiór {1} z {4,2,3}.
6 0 5
4 2 3
1
Minimalne drzewo rozpinajÄ…ce
Minimalne drzewo rozpinające to zbiór krawędzi łączących wszystkie wierzchołki
grafu, których suma (biorąc pod uwagę wagi krawędzi) jest minimalna. Graf wyznaczony
przez krawędzie minimalnego drzewa rozpinającego nie posiada cykli, a zatem, jak sama
66
Algorytmy i struktury danych
nazwa wskazuje jest to drzewo. Istnieją przykłady grafów, które posiadają więcej ni\
tylko
jedno minimalne drzewo rozpinajÄ…ce. Poni\
ej omówiono dwa algorytmy pozwalające
wyznaczyć minimalne drzewo rozpinające w dowolnym grafie.
Algorytmy zostały omówione na przykładzie problemu, polegającego na wybraniu z
zaproponowanych do pobudowania dróg tych, których całkowity koszt będzie minimalny.
Koszt budowy danej drogi to waga krawędzi. Poni\
ej przedstawiono graf oraz jego macierz
sąsiedztwa dla omówionego problemu.
A B C D E F G H I
A 0 4 0 0 0 0 0 8 0
B 4 0 8 0 0 0 0 11 0
C 0 8 0 7 0 4 0 0 2
D 0 0 7 0 9 14 0 0 0
E 0 0 0 9 0 10 0 0 0
F 0 0 4 14 10 0 2 0 0
G 0 0 0 0 0 2 0 1 6
H 8 11 0 0 0 0 1 0 7
I 0 0 2 0 0 0 6 7 0
8 7
4
B C D
A
2
11
8 14 9
4
I
7
6
H E
1 2 10
F
G
Algorytm Kruskala
Algorytm Kruskala jest algorytmem zachłannym pozwalający rozwiązać powy\
sze
zadanie. Algorytm zachłanny to taki, który nie martwi się tym, co będzie póz
niej, wybiera
najlepsze rozwiÄ…zanie w danym momencie.
Aby znalez
ć minimalne drzewo rozpinające postępujemy w następujący sposób.
Sortujemy rosnąco wagi i rozpoczynamy od najmniejszej. Bierzemy krawędz
o najmniejszej
wadze i patrzymy, czy warto wybudować tę drogę. To czy warto określamy w następujący
sposób. Dana krawędz
Å‚Ä…czy dwa miasta, je\
eli sÄ… one w tym samym zbiorze (majÄ… tego
samego lidera), to nie warto budować tej drogi. W przeciwnym wypadku budujemy drogę i
łączymy zbiory, do których nale\
ały wspomniane miasta. Na początku wszystkie miasta
będą tworzyły zbiory jednoelementowe, gdy\
nie będą jeszcze połączone. Stopniowo
będziemy scalać miasta.
Kolejne kroki dla omawianego grafu będą następujące:
67
Algorytmy i struktury danych
1. droga H-G, warto ją pobudować  wierzchołki nie są w tym samym zbiorze;
2. droga G-F, warto ją pobudować  wierzchołki nie są w tym samym zbiorze;
3. droga I-C, warto ją pobudować  wierzchołki nie są w tym samym zbiorze;
4. droga A-B, warto ją pobudować  wierzchołki nie są w tym samym zbiorze;
5. droga C-F, warto ją pobudować  wierzchołki nie są w tym samym zbiorze;
6. droga I-G, nie budujemy gdy\
te miasta sÄ… ju\
połączone  są w tym samym
zbiorze;
7. droga C-D, warto ją pobudować  wierzchołki nie są w tym samym zbiorze;
8. droga H-I, nie budujemy gdy\
te miasta sÄ… ju\
połączone  są w tym samym
zbiorze;
9. droga B-C, warto ją pobudować  wierzchołki nie są w tym samym zbiorze;
10. droga A-H, nie budujemy gdy\
te miasta sÄ… ju\
połączone  są w tym samym
zbiorze;
11. droga D-E, warto ją pobudować  wierzchołki nie są w tym samym zbiorze;
12. pozostałych dróg nie budujemy gdy\
miasta sÄ… ju\
połączone  wszystkie są w
jednym zbiorze.
Stosując algorytm Kruskala otrzymaliśmy dla naszego grafu poni\
sze minimalne
drzewo rozpinające. Suma wag wszystkich krawędzi wynosi 37. Jak się oka\
e za chwile (dla
algorytmu Prima) dla tego grafu istniejÄ… tak\
e inne minimalne drzewa rozpinające. Końcowa
postać tego drzewa zale\
y od decyzji, jakie podejmiemy rozpatrując kolejne krawędzie.
Je\
eli istnieją krawędzie o takich samych wagach, to kolejność wybór zadecyduje o postaci
końcowej drzewa. Zawsze jednak suma wag w ka\
dej wersji minimalnego drzewa
rozpinającego musi być taka sama  musi być minimalna.
8 7
4
B C D
A
2
9
4
I
H E
1 2
F
G
Algorytm Prima
Algorytm Prima to druga z metod szukania minimalnego drzewa rozpinajÄ…cego.
Rozpoczynamy analizę z dowolnego wierzchołka i wypisujemy mo\
liwe połączenia
bezpośrednie z innymi węzłami. Następnie wybieramy krawędz
o najmniejszej wadze.
Połączy ona nasze miasto z innym. Następnie wypisujemy mo\
liwe połączenia dla tego
nowego (dołączonego) miasta. Tutaj jest jednak pewna zasada. Je\
eli wcześniej wypisane
połączenie z jakimś miastem jest bardziej atrakcyjne ni\
to, które wypisujemy obecnie to
pozostawiamy poprzednie. Po wypisaniu tych mo\
liwości znów wybieramy krawędz
o
minimalnej wadze. Czynności te wykonujemy dopóki nie zostaną połączone wszystkie
miasta.
Dokładną zasadę dla podanego grafu przedstawia poni\
sza tabela. AnalizÄ™
rozpoczynamy z miasta D i w kolumnach wypisujemy mo\
liwe połączenia z
rozpatrywanego miasta. Jeśli rozpatrujemy i-ty węzeł i nie ma on połączenia z węzłem w j-
tym wierszu to przepisujemy wartość z poprzedniej kolumny. Jeśli natomiast istniej
68
Algorytmy i struktury danych
połączenie, to sprawdzamy, czy jest atrakcyjniejsze od wartości z poprzedniej kolumny. Jeśli
tak, to wpisujemy, w przeciwnym wypadku przepisujemy wartość z poprzedniej kolumny.
D C I F G H A B
A * * * * * 8 - -
B * 8 8(C) 8(C) 8(C) 8(C)<11 4 -
C 7 - - - - - - -
D - - - - - - - -
E 9 9(D) 9(D) 9(D)<10 9(D) 9(D) 9(D) 9(D)
F 14 4 4(C) - - - - -
G * * 6 2 - - - -
H * * 7 7(I) 1 - - -
I * 2 - - - - - -
*gwiazdka oznacza niemo\
liwość bezpośredniego połączenia tych miast, a    stawiamy w miejscu, gdzie
połączenie ju\
istnieje, połączenie miasta z tym samym miastem (np. D z D) istnieje od początku, wybraną
krawędz
zaznaczono na niebiesko.
7
4
B C D
A
2
8 9
4
I
H E
1 2
F
G
Najkrótsze ście\
ki z jednym z
ródłem
Problem polega na ustaleniu najkrótszej drogi (suma wag krawędzi, po których
będziemy się poruszać ma być minimalna) z dowolnie wybranego wierzchołka do
wszystkich pozostałych. Problem ten będziemy rozwa\
ać na przykładzie grafu
skierowanego z wagami, chocia\
mo\
na to samo zrobić na grafie nieskierowanym z wagami.
Do rozwiÄ…zania tego problemu mo\
emy wykorzystać jeden z dwóch algorytmów opisanych
poni\
ej.
Algorytm Dijkstry
Pierwszy krok to wybór wierzchołka z którego będziemy startować. Następnie
wykonujemy tzw. relaksację, czyli przejście po wszystkich sąsiadach i wyszukanie
najlepszego połączenia.
Najlepiej będzie rozwa\
yć to na konkretnym przykładzie. Analizując problem
będziemy opierać się na kilku zasadach. Je\
eli uda nam się ustalić ju\
krawędz
, którą
docieramy do danego wierzchołka to w tym wierzchołku zapamiętamy tak\
e, z którego
wierzchołka dotarliśmy do niego. W wierzchołku zapamiętujemy tak\
e sumę wag krawędzi,
którymi dotarliśmy do tego wierzchołka z wierzchołka startowego.
Oto przykładowy graf, w którym będziemy szukać najkrótszych połączeń.
69
Algorytmy i struktury danych
Suma wag, którą trzeba
pokonać aby tu dotrzeć oraz
" "
nazwa wierzchołka z którego
1
przyszliśmy.
B C
waga
10
0/N
9
A 2 3 4 6
5
2
D E
" "
7
Przyjmijmy, \
e chcemy znalez
ć najkrótsze drogi z wierzchołka A (chocia\
mo\
e to być
dowolnie inny wierzchołek) do dowolnego wierzchołka w grafie. Nad A wpisujemy 0, gdy\

z wierzchołka A do A trzeba pokonać drogę równą 0, nad pozostałymi wierzchołkami
wpisujemy wartość bardzo du\
Ä… (np. "). Ustalamy, \
e skoro z A startujemy to drogÄ™ do A
ju\
znamy (oznaczamy to niebieskim kolorem).
Kolor oznacza, \
e
znamy ju\
drogÄ™ do
10
"
tego wierzchołka.
1
B C
10
0
9
A 2 3 4 6
5
2
D E
"
5
7
Teraz sprawdzamy wszystkie mo\
liwe połączenia od wierzchołka A do ka\
dego innego
wierzchołka, do którego nie znamy jeszcze drogi.
z A do A Ju\
mamy połączenie.
z A do B Jest takie połączenie o wadze 10.
z A do C Nie ma połączenia, więc droga, którą nale\
y przebyć pozostaje ".
z A do D Jest takie połączenie o wadze 5.
z A do E Nie ma połączenia, więc droga, którą nale\
y przebyć pozostaje ".
Teraz z pośród grupy wierzchołków do których jeszcze nie ustaliliśmy drogi wybieramy
wartość najmniejszą (z tych wartości zapisanych obok wierzchołków). U nas jest to krawędz

o wadze 5, prowadząca do wierzchołka D, wiedzie on z wierzchołka A. Znamy ju\
drogÄ™ do
D.
70
Algorytmy i struktury danych
8 14
1
B C
10
0
9
A 2 3 4 6
5
2
D E
5/A 7
7
W następnym kroku analizujemy połączenia wychodzące z D. Tu jednak obowiązuje pewna
zasad, o której jeszcze nie wspomniałem. Je\
eli połączenie z D do i-tego wierzchołka będzie
miało większą sumę wag, ni\
ta, która ju\
jest wpisana w i-tym wierzchołku, to nie
zamieniamy tej wartości. W przeciwnym wypadku podmieniamy wartość.
z D do A Ju\
mamy połączenie.
z D do B 5 (droga z A do D) + 3 (z D do B) daje 8. To jest mniejsze od 10, więc wstawiamy 8.
z D do C 5 + 9 daje 14, co jest mniejsze od ".
z D do D Ju\
mamy połączenie.
z D do E 5 + 2 daje 7 co jest mniejsze od ".
Teraz znów wybieramy minimum z pośród nie ustalonych jeszcze połączeń. Będzie to 7,
więc idziemy z D do E.
8 13
1
B C
10
0
9
A 2 3 4 6
5
2
D E
5/A 7/D
7
Teraz przeglądamy połączenia z E:
z E do A Ju\
mamy połączenie.
5 (droga z A do D) + 3 (D do B) daje 8. To pozostawiamy, gdy\
połączenie z E do B jest równe ",
z E do B
a to więcej ni\
8.
z E do C 7 + 6= 13 co jest mniejsze od 14, więc zamieniamy na 13
z E do D Ju\
mamy połączenie.
z E do E Ju\
mamy połączenie.
71
Algorytmy i struktury danych
Minimum jest równe 8, więc idziemy z D do B.
8/D 9
1
B C
10
0
9
A 2 3 4 6
5
2
D E
5/A 7/D
7
Analizujemy połączenia z B:
z B do A Ju\
mamy połączenie.
z B do B Ju\
mamy połaczenie.
z B do C 8 + 1 jest mniejsze od 13, więc zamieniamy na 9
z B do D Ju\
mamy połączenie.
z B do E Ju\
mamy połączenie.
Jest tylko jeden element, więc on będzie minimum.
8/D 9/B
1
B C
10
0
9
A 2 3 4 6
5
2
D E
5/A 7/D
7
Na powy\
szym grafie mamy gotowe rozwiÄ…zanie dla ka\
dego wierzchołka.
Przykładowo: aby dowiedzieć się jak dotrzeć z A do C, nale\
y sprawdzić skąd dotarto do C
 nad wierzchołkiem pisze, \
e z B. Teraz sprawdzamy skąd doszliśmy do B  z D. Z kolei do
D doszliśmy z A. A więc droga z A do C biegnie przez D oraz B i jest to najkrótsza mo\
liwa
droga o sumie wag równej 9.
Niestety algorytm ten mo\
e nie zadziałać poprawnie w przypadku, gdy w grafie są
ujemne wagi. To samo w sobie nie jest groz
ne. Problem pojawia się, gdy w grafie występują
cykle, których suma wag jest ujemna. Wtedy algorytm się zapętli. Przykładowy fragment
grafu mamy narysowany poni\
ej. PoszukujÄ…c rozwiÄ…zania zgodnie z algorytmem Dijkstry z
wierzchołka A pójdziemy do B. W następnym kroku z B przejdziemy do A. Potem
stwierdzimy, \
e idąc znów do B nasza droga się skróci. W efekcie suma wag będzie
72
Algorytmy i struktury danych
wyglądał następująco 2-8+2-8+& +2-8. Będzie w ka\
dym przejściu cyklu malała, do czego
algorytm dÄ…\
y. Spowoduje to jednak zapętlenie.
B
2 -8
A
Algorytm Bellmana  Forda
Algorytm Bellmana - Forda zabezpiecza nas przed wspomnianymi ju\
ujemnymi
cyklami w grafie. Kolejne kroki algorytmu są następujące:
Najpierw ustalamy, \
e droga z dowolnie wybranego wierzchołka do wszystkich
pozostałych jest bardzo długa- wstawiamy " w miejsce, gdzie pamiętamy długość
drogi.
Następnie w pętli n-1 razy (gdzie n to ilość węzłów) robimy relaksację.
W ostatnim kroku nale\
y sprawdzić, czy wystąpiły cykle ujemne, jeśli nie to
algorytm zadziałał poprawnie.
Rozwa\
my przykładowy graf. Poszukujemy najkrótszych ście\
ek z wierzchołka A do
wszystkich pozostałych wierzchołków. Na poni\
szym rysunku wstawiono ju\
poczÄ…tkowe
odległości do wszystkich wierzchołków.
5
" "
B C
-2
6
0
-4
A 8 7
7 -3
9
D E
" "
2
Rozwa\
ania tego algorytmu będą zapisywane w tabeli. Wartości w i-tej kolumnie,
będą informowały nas jaką drogę trzeba przebyć do i-tego wierzchołka i skąd przyszliśmy.
Poszczególne wiersze reprezentują kolejne kroki algorytmu. Przy ka\
dej odległości w
indeksie dolnym podano z którego wierzchołka dotarliśmy. Symbol nieskończoności
oznacza brak bezpośredniego sąsiedztwa.
W zerowym kroku zawsze wpisujemy do tabeli wartości wag z macierzy incydencji.
Jeśli chcemy znalez
ć połączenia z wierzchołka A, to wpisujemy odległości wierzchołka A do
wszystkich pozostałych.
73
Algorytmy i struktury danych
krok wierz. A wierz. B wierz. C wierz. D wierz. E
0 0A 6A " 7A "
Teraz rozwa\
amy wszystkie krawędzie wchodzące do ka\
dego z wierzchołków i sprawdzamy czy uzyskana
droga będzie krótsza od tej ju\
danej.
6B + 5
0A + 6 0A + 7 7D + 9
"E + 2 > 0 7D -3
"C - 2 6B + 8 6B  4
1 nie zamieniamy "E + 7
nie zamieniamy nie zamieniamy zamieniamy
zamieniamy
0A 6A 4D 7A 2B
6B + 5
0A + 6 0A + 7 7D + 9
2E + 2 7D  3
4C  2 6B + 8 6B -4
2 nie zamieniamy 2E + 7
zamieniamy nie zamieniamy nie zamieniamy
nie zamieniamy
0A 2C 4D 7A 2B
2B + 5
0A + 6 0A + 7 7D + 9
2E + 2 7D -3
4C -2 2B + 8 2B  4
nie zamieniamy 2E + 7
nie zamieniamy nie zamieniamy zamieniamy
3 nie zamieniamy
0A 2C 4D 7A -2B
2B + 5
0A + 6 0A + 7 7D + 9
-2E + 2 7D -3
4 4C -2 2B + 8 2B  4
nie zamieniamy -2E + 7
nie zamieniamy nie zamieniamy nie zamieniamy
nie zamieniamy
W kroku pierwszym do wierzchołka A prowadzi krawędz
z E. Z poprzedniego kroku
wiemy, \
e, aby dotrzeć do E nale\
y przebyć drogę nieskończenie długą ("E). Zatem suma
tego co nale\
y przebyć do E oraz odległości A od E jest większa od obecnej wartości dla A.
W tej sytuacji nie podmieniamy tych wartości. Do wierzchołka B prowadzą dwie drogi, z A
oraz C. Obliczmy sumę dla obu przypadków (0A + 6 oraz "C  2). śadna z nich nie jest
mniejsza od istniejącej więc znów nie podmieniamy wartości. Kolejny wierzchołek to C.
Tutaj prowadzą krawędzie z B, D oraz E. Po obliczeniu sum okazuje się, \
e droga z
wierzchołka D będzie krótsza od tej, którą obecnie mam ustaloną  zatem podmieniamy
wartości. Te same czynności wykonujemy dla wszystkich pozostałych wierzchołków n-1
razy (gdzie n to ilość wierzchołków).
Po wykonaniu n-1 kroków nale\
y jeszcze sprawić, czy nasz graf nie ma cykli
ujemnych. Poniewa\
tym celu wykonujemy jeszcze jeden dodatkowy krok, po którym
sprawdzamy, czy coś się zmieniło w naszych ustaleniach. Jeśli nie, to oznacza to, \
e w grafie
nie ma cykli ujemnych, Poniewa\
znalezione minimalne ście\
ki sÄ… poprawne.
Dla przykładu odczytajmy z tabeli najkrótszą ście\
kę z wierzchołka A do E.
Rozpoczynamy od końca. Najpierw sprawdzamy skąd dotarliśmy do E  był to wierzchołek
B (informacja o tym jest zapisana w dolnym indeksie). Z kolei do B dotarliśmy z C. Do
wierzchołka C przyszliśmy z D, a do D z A. Droga jaką nale\
y przebyć z A do E jest podana
bezpośrednio w kolumnie E i wynosi -2.
Maksymalny przepływ
Aby określić trasy, którymi mo\
na będzie przesyłać dane, rzeczy lub cokolwiek
innego, w jak największej ilości nale\
y obliczyć maksymalną przepustowość. Pozwoli ona
optymalnie pokierować naszymi danymi, aby jak najwięcej dotarło z punktu A do B.
Przykładem zastosowania tego algorytmu mo\
e być sieć komputerowa. Mo\
na jÄ…
przedstawić za pomocą grafu skierowanego, w którym wagi oznaczają ilość bajtów, które
mo\
na przesłać daną krawędzią (określają przepustowość). Przykład takiej sieci podano na
poni\
szym rysunku. Spróbujemy dla tego grafu określić maksymalną przepustowość
przesyłu danych z wierzchołka 0 do 5. Na początku przechodzimy graf szukając dowolnej
drogi z punktu 0 do 5. Mo\
e to być np. droga 0->1->2->5 zaznaczona na niebiesko.
74
Algorytmy i struktury danych
Maksymalna ilość danych jakie mo\
na naraz przesłać tą trasą wynosi 12, gdy\
tyle wynosi
waga krawędzi mającej najmniejszą przepustowość.
12
1 2
16 20
0 4 10 9 7 5
13
4
14
3 4
Rysujemy graf, na który będziemy zaznaczać wykorzystane ju\
drogi  nazwijmy go grafem
maksymalnej przepustowości. Pierwsza z nich wiedzie przez wierzchołek 1 oraz 2 i ma
przepustowość 12.
12
1 2
12 12
0 5
3 4
Teraz tworzymy tzw. graf mo\
liwości. Powstaje on wg pewnej zasady. Krawędzie nie
wykorzystane nie zmieniają się, natomiast w miejsce krawędzi wykorzystanych rysujemy
krawędzie o pozostałej do wykorzystania przepustowości oraz krawędzie nawrotów (na
czerwono). Przykładowo: krawędz
0->1 miała przepustowość 16, my wykorzystaliśmy 12,
więc pozostało 4. Krawędz
nawrotów to krawędz
, która powoduje tzw. nawracanie danych,
gdyby się okazało to konieczne. Krawędzie nawrotów to krawędzie narysowane na
powy\
szym grafie, ale z przeciwnymi zwrotami. Oto nasz graf mo\
liwości:
12
12 1 2
12
4
8
0 4 10 9 7 5
13
4
14
3 4
Powy\
sze czynności (przechodzenie grafu, dorysowanie wybranej drogi do grafu
maksymalnej przepustowości i tworzenie grafu mo\
liwości) wykonujemy dopóty, dopóki da
się przejść z wierzchołka 0 do 5. W naszym przykładzie udał się znalez
ć kolejną drogę, która
wiedzie z 0 przez 3 oraz 4 do 5. Jej maksymalna przepustowość wynosi 4. Dorysowujemy ją
do grafu maksymalnej przepustowości.
75
Algorytmy i struktury danych
12
1 2
12 12
0 5
4 4
4
3 4
Tworzymy graf mo\
liwości:
12
12 1 2
12
4
8
0 4 10 9 7 5
9
10 4
3 4
4
4
Przechodzimy graf i wybieramy drogę 0->3->4->2->5 (o maksymalnej przepustowości
równej 7). Dorysowujemy ją do grafu maksymalnej przepustowości.
12
1 2
12 12+7=19
0 7 5
4+7=11 4
4+7=11
3 4
Tworzymy graf mo\
liwości:
12
12 1 2
12+7=19
4
1
0 4 10 9 7 5
2
3 4
3 4
4+7=11
4+7=11
Teraz po przejściu grafu okazuje się, \
e nie ma ju\
drogi z wierzchołka 0 do 5, a więc
ustaliliśmy drogi dla przesyłania danych. Maksymalnie naraz mo\
emy wysyłać 23 jednostki
danych, co obrazuje poni\
szy graf maksymalnej przepustowości.
76
Algorytmy i struktury danych
12
1 2
12 12+7=19
0 7 5
4+7=11 4
4+7=11
3 4
Oczywiście pozostaje pytanie, w jaki sposób przechodzić dany graf: w głąb czy
wszerz? Pierwszy ze sposobów określa się mianem algorytmu Forda-Fulkersona, drugi 
metodą Edmunda-Karpa. Warto jednak zaznaczyć, \
e przechodzenie grafu wszerz mo\
e
okazać się efektywniejsze w przypadku niektórych grafów, w których wartości wag ró\
niÄ… siÄ™
znaczÄ…co.
Maksymalne skojarzenia w grafie dwudzielnym
Je\
eli dany zbiór wierzchołków da się podzielić na dwa podzbiory i wierzchołki
jednego podzbioru są połączone tylko z wierzchołkami z drugiego podzbioru to mamy do
czynienia z grafem dwudzielnym. Taką definicję podałem ju\
wcześniej. Teraz chciałbym
wspomnieć nieco o poszukiwaniu maksymalnych skojarzeń oraz maksymalnej
przepustowości w grafie dwudzielnym.
Przykładowo mamy elektrownie (ka\
da produkuje pewną ilość energii) i mamy
odbiorców. Nale\
y tak poprowadzić sieć, aby zaspokoić potrzeby wszystkich odbiorców
najlepiej jak się da. Aby rozwiązać ten problem nale\
y znalez
ć maksymalną przepustowość
takiej sieci energetycznej.
Super Super
wejście wyjście
Do rozwiÄ…zania zadania mo\
emy wykorzystać algorytm omówiony w poprzednim punkcie.
Wystarczy wprowadzić dodatkowo tzw. super wejście i super wyjście, które będą łączyły się
z wejściami i wyjściami krawędziami o " przepustowości (pozostałe krawędzie mogą mieć
dowolną wagę). Przykład takiego rozwiązania pokazano na powy\
szym rysunku, dodatkowe
krawędzie narysowano na czerwono. Teraz postępujemy tak, jak zostało to omówione
przepustowość punkcie poprzednim  wykorzystując podany tam algorytm.
Drugie z zadań, to znalezienie maksymalnego skojarzenia. Chodzi o to, aby jak
stworzyć jak najwięcej par węzłów z jednej i drugiej grupy, ale tak, aby ka\
dy z węzłów był
77
WYJÅšCIA
WEJÅšCIA
Algorytmy i struktury danych
skojarzony tylko raz. SytuacjÄ™ w takim grafie rozwiÄ…zujemy identycznie, jak w powy\
szym
przykładzie, poprzez wprowadzenie super wejścia i super wyjścia. Ró\
nica dotyczy jedynie
wag w grafie. Tu wszystkie wagi (zarówno krawędzi zwykłych, jak i krawędzi łączących
super wejście i wyjście) mają wartości jednakowe, np. 1. W kolejnych krokach postępujemy
tak jak w poprzednim punkcie.
Super Super
wejście wyjście
Obliczanie wielomianu chromatycznego
Omawiany tutaj problem ma szeroki zakres zastosowań. Przykładem mo\
e być,
chocia\
by problem pokolorowania mapy politycznej w taki sposób, aby sąsiedzi nie byli tego
samego koloru, a tak\
e, aby zu\
yć jak najmniejszą ilość kolorów. Innym problemem jest
kolorowanie wierzchołków grafu. I właśnie na tym zagadnieniu się skupimy. Chodzi o to,
\
eby tak pokolorować wierzchołki grafu, aby sąsiedzi byli pomalowani na inny kolor. Wez
my
sobie przykładowy, prosty graf.
2
1
3
Je\
eli zało\
ymy, \
e mamy do dyspozycji n kolorów, to rozpoczynając np. od wierzchołka 2,
mo\
emy go pokolorować na n sposobów. Jednak kolejny wierzchołek (np. 3) mo\
emy
pokolorować ju\
na n-1 sposobów, gdy\
nie wolno wykorzystać tego samego koloru, co dla
wierzchołka 2. Natomiast ostatni wierzchołek (1) mo\
emy pokolorować na n-2 sposobów,
poniewa\
nie wolno nam wykorzystać kolorów u\
ytych dla 2 i 3. Ilość sposobów na jaki
mo\
na pokolorować cały graf to iloczyn mo\
liwości dla ka\
dego wierzchołka.
Ç (x) = x(x -1)(x - 2)
Wielomian ten nazywamy wielomianem chromatycznym.
Rozwa\
my jeszcze klika przykładów. Obok ka\
dego z wierzchołków napisałem na ile
sposobów mo\
na go pomalować. Dla uniknięcia zamieszania rozpoczynam malowanie od
pierwszego, a kończę na ostatnim wierzchołku.
78
Algorytmy i struktury danych
2 (n-1)
3 (n-1) 1 (n)
2 (n)
1 (n)
4 (n-2)
3 (n-1)
4 (n-2)
5 (n-2)
2 2
Ç(x) = x (x -1)(x - 2) Ç(x) = x(x -1)2 (x - 2)
Ogólny wzór wielomianu chromatycznego przedstawia się zatem następująco:
Ç(G) = Ç(G \ {e}) - Ç(G -{e})
gdzie:
G- to graf dla którego obliczamy wielomian;
G\{e}- to ten sam graf bez usuniętej krawędzi;
g-{e}- to ten sam graf, ale ze sklejonymi wierzchołkami, które usunęliśmy.
Znaczenie tego zapisu najlepiej wyjaśnić na przykładzie. Oto równanie grafów:
e
graf G graf G bez krawędzi e graf G ze sklejonymi wierzchołkami
A teraz obliczmy wielomian dla grafu G. Stosujemy tutaj rekurencję. Po rozło\
eniu tego grafu
(jw.) rozkładamy oba te grafy tak długo, a\
nie będą miały one krawędzi. Warto od razu
zauwa\
yć, \
e niektóre konfiguracje grafu będziemy rozkładać kilka razy, dlatego wypada w
implementacji zastosować programowanie dynamiczne. Na czerwono zaznaczam krawędzie
do usunięcia w kolejnych krokach.
79
Algorytmy i struktury danych
Przypominam, \
e nasz wielomian wcześniej dla identycznego grafu wyniósł:
Ç(x) = x(x -1)2 (x - 2) = x4 - 4x3 + 5x2 - 2x
Z powy\
szego rysunku idzie równie\
odczytać ten sam wielomian. Ilość wierzchołków w
ka\
dym z czynników sumy to wykładnik potęgi do której podnosimy x. dla naszego
przykładu wielomian będzie wyglądał następująco:
x4 - x3 - x3 + x2 - x3 + x2 - x3 + x2 + x2 - x + x2 - x =
x4 - 4x3 + 5x2 - 2x
80
Algorytmy i struktury danych
Dodatek: Algorytmy wyszukiwania wyrazu wzorcowego w
tekście
Metoda  naiwna
Pierwsza z metoda polega na porównywaniu pierwszego znaków wzorca z pierwszym
znakiem tekstu, gdy jest zgodny to porównujemy kolejne znaki. Je\
eli któryś nie będzie
zgodny, to przerywamy porównywanie i rozpoczynamy znów od początku wzorca, ale tym
razem porównujemy z kolejnymi znakami tekstu (1 znak wzorca z 2 znakiem tekstu, itd.).
Najlepiej pokazać to na przykładzie. Mamy dany tekst: abcaacaabcbacab oraz wzorzec aab.
Na czerwono zaznaczam zgodne znaki w porównaniu.
a b c a a c a a b c b A c a b
a a b
a b c a a c a a b c b A c a b
a a b
a b c a a c a a b c b A c a b
a a b
a b c a a c a a b c b A c a b
a a b
a b c a a c a a b c b A c a b
a a b
a b c a a c a a b c b A c a b
a a b
a b c a a c a a b c b A c a b
a a b
Metoda ta nie jest zbyt efektywna, poniewa\
w przypadku długiego wzorca, gdy
napotykamy na prawie dobry ciąg, ale ró\
niący się jedynie końcówką, to cała nasza praca
związana z porównaniem tego tekstu idzie na marne, przesuwamy wzorzec jedynie o jedną
pozycję i musimy zaczynać porównywanie od nowa.
Metoda Rabina-Karpa
Jest to o wiele bardziej efektywna metoda. Polega na porównywaniu nie pojedynczych
znaków, lecz całego ciągu. Ka\
dy znak jest reprezentowany przez jakąś liczbę (przykładem
mo\
e być kod ASCII). Je\
eli potraktujemy porównywany ciąg znaków jak liczbę zapisaną w
pewnym systemie liczbowym, to przyspieszy nam to algorytm. W naszym przykładzie
będziemy rozpatrywać tekst składający się z trzech znaków, a zatem będziemy działać na
kodzie trójkowym. Przyjmijmy, \
e a to 0, b=1, c=2. Zatem przykładowy ciąg znaków aabc
mo\
emy potraktować jako liczbę (0012)3 w kodzie trójkowym.
(0012)3 = 0 Å" 33 + 0 Å" 32 +1Å" 31 + 2 Å" 30 = (5)10
Obliczanie takiego wielomianu nie jest zbyt dobre dla kompilatora. On strasznie nie lubi
podnosić do potęgi. Dlatego najlepiej zastosować schemat Kornera dla obliczenia takiej
wartości. Idea tego schematu jest następująca:
a0 xn + a1xn-1 + a2 xn-2 + ... + an x0 = (((a0 x + a1)x + a2 )x + ...)x + an
Taki sposób obliczania wielomianu znacznie ułatwia pracę komputerowi. Rozpatrzmy jakiś
przykład. Mamy dany tekst: abcabbcbbcab oraz wzorzec: bbcb. Poniewa\
wzorzec jest cztero
81
Algorytmy i struktury danych
cyfrowy, więc będziemy porównywać liczby czterocyfrowe zapisane w systemie trójkowym.
Na początku obliczamy wartość wzorca- zamieniamy ją na system dziesiętny:
1121 = ((1Å" 3 +1) Å" 3 + 2) Å" 3 +1 = 43
A teraz to samo robimy dla pierwszych czterech (poniewa\
taka jest długość wzorca) znaków
tekstu:
0120 = ((0 Å" 3 +1) Å" 3 + 2) Å" 3 + 0 = 15
Dla uproszczenia zdefiniujmy sobie liczbę 15 jako wartość. Teraz porównujemy wartość z 43
je\
eli są równe to oznacza, \
e to jest nasz szukany wzorzec, je\
eli nie to nale\
y sprawdzić z
następnym ciągiem (z ciągiem bcab). Tu jednak pewna uwaga. Nie trzeba obliczać jego
wartości z schematu Kornera, jest prostszy wzór:
(wartosc - tekst[i]Å" podstawadlugosc ) Å" podstawa + tekst[i + dlugosc]
gdzie:
wartość- to zmienna wartość, czyli poprzedni ciąg znaków;
tekst- to tablica, w której przechowujemy przeszukiwany tekst;
i- to indeks w tej tablicy, od którego zaczyna się analizowany tekst;
postawa- to podstawa systemu kodowania, który stosujemy (w naszym przykładzie
jest to 3);
długość- to długość wzorca (ilość znaków).
bcab(1201) = (15 - 0 Å" 27) Å" 3 +1
A zatem nasze porównania będą wyglądać następująco:
Wartość wzorzec wynik
abca (15) bbcb (43) ró\
ne
bcab (46) bbcb (43) ró\
ne
cabb (58) bbcb (43) ró\
ne
abbc (14) bbcb (43) ró\
ne
bbcb (43) bbcb (43) równe
Jedynym problemem jaki mo\
e się pojawić w przypadku tego algorytmu, to problem zbyt
długiego słowa. W przypadku alfabetu mamy do czynienia z dość znaczną ilość znaków, a co
za tym idzie dość du\
ymi liczbami. Jednak wtedy mo\
na zastosować dzielenie tych liczb
modulo. Prawdopodobieństwo, \
e uzyskamy te same wyniki przy dzieleniu dwóch tak du\
ych
liczb jest praktycznie zbli\
one do zera.
Metoda Knuta-Morrisa-Pratta
Jest to udoskonalona metoda  naiwna . Udoskonalenie polega na wprowadzeniu
funkcji prefiksowej, dzięki której zapamiętujemy dotychczasowe porównania i w wypadku,
gdy nasz porównywany wzorzec nie będzie zgodny pod koniec jego porównywania, to nie
przesuwamy go o jedną pozycję, ale o tyle, ile mówi nam funkcja prefiksowa. Rozwa\
Ä™ tutaj
jedynie przykład pokazujący idę tego algorytmu, nie skupię się na sposobie wyznaczania
funkcji prefiksowej, która jest inna dla ka\
dego wzorca. Mamy tekst: abcaabcbab oraz
wzorzec: bcb.
82
Algorytmy i struktury danych
a b c a A b c b a b c b a b c
b c b
Znaki są niezgodne więc przesuwamy wzorzec o 1.
a b c a a b c b a b c b a b c
b c b
1 i 2 znak jest OK, ale 3 ju\
nie. Jednak nie przesuwamy wzorca o 1 gdy\
1 jego znak na pewno nie będzie
zgodny z 3 i 4 w tekście (stwierdzenie na podstawie funkcji prefiksowej).
a b c a a b c b a b c b a b c
b c b
1 znak się nie zgadza więc przesuwamy wzorzec o 1.
a b c a a b c b a b c b a b c
b c b
Znalez
liśmy wzorzec.
Zakończenie
Notatki te powstały w ramach przygotować do egzaminu z przedmiotu  Algorytmy i
struktury danych . Mogą zawierać błędy, za które nie biorę \
adnej odpowiedzialności. Będę
wdzięczny za wszelkie uwagi mogące pomóc mi poprawić ewentualne niedociągnięcia.
83