Grafovi su jedna od najkorisnijih struktura podataka. Još u davna vremena su korišćeni za predstavljanje mreža puteva između gradova i odgovarajućih mapa, koje su putnici nosili sa sobom tokom putovanja. Poznat je slučaj kopije mape iz petog veka koja je sadržala mrežu puteva Rimskog carstva sa nazivima gradova i dužinama puteva između njih, koja je pružala dovoljno informacija potrebnih da se pronađe najkraći put između dva grada. Još jedna od klasičnih primena grafova (specijalno drveta) je predstavljanje genealogija. Naime, porodična stabla su vekovima korišćena u svrhe odgovora na pravna pitanja poput pitanja dozvoljenih brakova, nasledstva i nasleđivanja vlasti. Naravno, postoji mnogo drugih poznatih primera primena grafova, kao što su predstavljanje strana i ivica poliedara, komunikacione mreže, električna kola, strukturne formule molekula, društvene igre, traženje izlaza iz lavirinta, a u današnje vreme veoma popularna primena je za modelovanje odnosa korisnika na društvenim mrežama.
U ovom poglavlju upoznaćemo se sa pojmom grafa, načinima na koje se on može predstaviti u računaru, a zatim i osnovnim grafovskim algoritmima. Najpre ćemo razmotriti dva osnovna algoritma za obilazak grafa: obilazak u dubinu i obilazak u širinu, kao i karakteristike grafova u odnosu na ove dve vrste pretrage. Nakon toga bavićemo se pitanjem povezanosti grafa: razmotrićemo algoritme za određivanje komponenti povezanosti u neusmerenom, odnosno komponenti jakih povezanosti u usmerenom grafu, kao i algoritmima za određivanje mostova i artikulacionih tačaka u grafu.
Razmotrićemo svojstva acikličkih usmerenih grafova, kao i algoritme za konstrukciju topološkog sortiranja grafa. Videćemo na koji način se poznavanje topološkog sortiranja može iskoristiti za efikasno određivanje najkraćih puteva od jednog do svih ostalih čvorova u acikličkom grafu.
Biće reči i o algoritmima za utvrđivanje da li u datom grafu postoji Ojlerov, odnosno Hamiltonov put (ciklus), tj. put (ciklus) koji kroz svaku granu grafa, odnosno kroz svaki čvor grafa prolazi tačno jednom. Pokazuje se da su ova dva problema iako naizgled jako bliska sasvim različite težine i da se pristupi njihovom rešavanju veoma razlikuju.
Bavićemo se, takođe, različitim problemima koji se bave težinskim grafovima i određivanjem najkraćih puteva u grafu, i to konkretno: Dajkstrinim i Belman-Fordovim algoritmom za određivanje najkraćih puteva od jednog fiksiranog čvora i Flojd-Varšalovim algoritmom za računanje najkraćih čvorova između svaka dva čvora u grafu.
Konačno, prikazaćemo dva različita algoritma za konstrukciju minimalnog povezujućeg drveta datog grafa.
Poglavlja: