UNIVERZITET SINGIDUNUM
Dejan Živkovi
ć
U VO D U A L G O R I T M E I
S T RU K T U R E P O DATA K A
Prvo izdanje
Beograd, 2010.
Predgovor
Oblast algoritama i struktura podataka potvrdila je svoje mesto u ra-
ˇcunarstvu zbog praktiˇcne važnosti i teorijske elegancije. Sa jedne strane,
praktiˇcari mogu da neposredno koriste dobre algoritme i efikasne struk-
ture podataka u složenim programskim projektima. Sa druge strane, za
istraživaˇce su algoritmi važan alat kojim se meri stepen složenosti nekog
raˇcunarskog problema. Algoritmi i strukture podataka se nalaze u centru
svih metodologija koje se koriste u radu sa savremenim raˇcunarima. Mada
na prvi pogled možda tako ne izgleda, neka napredna metodologija sigurno
se temelji na sofisticiranim algoritmima i strukturama podataka.
Cilj ove knjige je da ˇcitaocima predstavi osnove ove fascinantne oblasti
raˇcunarstva. Radi toga se u knjizi prevashodno razmatraju neke od najo-
snovnijih metoda i paradigmi za dizajniranje i analiziranje struktura po-
dataka i algoritama. Pri tome je pokušano da se naglasak stavi na idejama
i lakšem razumevanju koncepata, a ne na implementacionim detaljima.
Ova knjiga je primarno zamišljena kao fakultetski udžbenik za prvo
upoznavanje sa algoritmima i strukturama podataka na prvoj ili drugoj
godini studija raˇcunarstva. Razumevanje materijala iz knjige zahteva ba-
ziˇcno predznanje iz raˇcunarstva i matematike. Konkretnije, od ˇcitalaca
se oˇcekuje da imaju iskustva u pisanju programa na nekom programskom
jeziku višeg nivoa kao što su Pascal, C ili Java. Pretpostavlja se i da ˇcitaoci
poznaju osnovne matematiˇcke koncepte u koje spadaju skupovi, funkcije i
indukcija.
U knjizi se nalazi preko 150 slika i tabela koje služe za ilustraciju
materijala. Algoritmi u tekstu su navedeni na jednostavnom pseudo jeziku
tako da ˇcitaoci ne moraju da uˇci novi programski jezik da bi razumeli
kako algoritmi rade. Dodatno, na kraju svakog poglavlja se nalazi više
zadataka ˇcija težina ide u rasponu od prostih vežbi za utvr ¯divanje izloženog
materijala pa do kreativnih problema. Ovi zadaci se smatraju integralnim
delom knjige i ˇcitaoci treba bar da pokušaju da ih reše.
ii
Predgovor
Zahvalnost.
Najdublju zahvalnost dugujem svima koji su mi pomogli u
pripremi ove knjige. Zahvaljujem se mnogim kolegama i studentima koji
su koristili radne verzije knjige i odgovorili na moj zahtev da predlože neka
poboljšanja i otkriju neizbežne greške.
Na kraju, bio bih veoma zahvalan ˇcitaocima na njihovom mišljenju o
knjizi. Svi komentari i prona ¯dene greške mogu se poslati elektronskom
poštom na adresu
[email protected]
.
D
EJAN
Ž
IVKOVI ´C
Beograd, Srbija
januar 2010.
iv
Sadržaj
6 Stabla
145
6.1 Korenska stabla . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
6.2 Binarna stabla . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6.3 Binarna stabla pretrage . . . . . . . . . . . . . . . . . . . . . . 155
6.4 Binarni hipovi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.5 Primene stabala . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7 Grafovi
185
7.1 Osnovni pojmovi i definicije . . . . . . . . . . . . . . . . . . . . 186
7.2 Predstavljanje grafova . . . . . . . . . . . . . . . . . . . . . . . 191
7.3 Obilazak grafa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
7.4 Obilazak usmerenog grafa . . . . . . . . . . . . . . . . . . . . . 209
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
8 Težinski grafovi
223
8.1 Osnovni pojmovi . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
8.2 Minimalno povezuju´ce stablo . . . . . . . . . . . . . . . . . . . 225
8.3 Najkra´ci putevi od jednog ˇcvora . . . . . . . . . . . . . . . . . . 236
8.4 Najkra´ci putevi izme ¯du svih ˇcvorova . . . . . . . . . . . . . . . 243
Zadaci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
Literatura
251
Indeks
253
