Grafovi

Neusmjereni graf sa 5 čvorova

Grafovi predstavljaju prirodan i dobar način za modeliranje nelinearnih relacija. Operacije sa grafovima su složenije nego sa drugim strukturama.

Ne postoji zasebna struktura zvana graf. Grafovi su najsličniji strukturi podataka stablo.

Definicije i osnovni pojmovi

Graf

Graf G je uređen par (V,E) gdje je V konačan neprazan skup, a skup E predstavlja binarne relacije elemenata skupa V. Elementi skupa V se nazivaju čvorovi, a elementi skupa E grane. Broj elemenata skupa V naziva se red grafa.

Usmjeren i neusmjeren graf

Ako su parovi čvora(u,v) koji odgovaraju granama uređeni,radi se o usmjerenom grafu,u suprotnom kažemo da se radim o neusmjerenim grafovima. Ako imamo kombinaciju usmjerenih i neusmjerenih grana onda za graf kažemo da je mješovit graf.

Ciklus

Ciklus u grafu je prost put koji počinje i završava se u istm čvoru. Graf je cikličan samo ako postoji barem jedan ciklus u datom grafu.

Predstavljanje grafova

U programskim jezicima ne postoji zasebna struktura podataka zvana graf. Grafove možemo predstavljati na sljedeća na sljedeća dva načina:

• matrica susjedstva
• lista susjedstva

Matrica susjedstva

Graf se može predstaviti matricom susjedstva A koja je kvadratna matrica forma nxn. Članove matrice a[i,j] predstavljamo pomoču binarnih vrijednosti:

• a[i,j]=1 ako grana (i,j)∈ E
• a[i,j]=0 ako grana (i,j)∉ E

Ovim načinom predstavljanja grafa predstavljamo sve grane posmatranog grafa, bez obzira da li ta grana postoji ili ne.

Lista susjedstva

Graf također možemo predstaviti i pomoću liste susjedstva. Ovakav način predstavljanja grafa ima formu da za svaki čvor grafa imamo listu.

Na osnovu liste susjedstva predstavljamo samo postojeće grane grafa. Kada je riječ o neusmjerenim grafovima ovakav način predstavljanja grafova je redudantan, jer svaka grana (u,v) pojavljivat će se dva puta u listama. Jednom u listi od čvora u,a drugi put u listi od čvora v.

Obilazak grafa

Rad sa grafovima podrazumjeva obilazak i prolazak tim istim grafom. Za razliku od stabla graf nema početnog definisanog čvora. Programerska praksa je da se taj čvor odabere slučajnim odabirom ili proslijedi kao parametar u funkciji algoritma. U slučaj da jedan čvor ima više susjeda, uvodi se dodatni vektor koji ima binarne vrijednosti i na početku stavimo 0 jer su svi čvorovi neposjećeni. Kada posjetimo prvi put čvor stavimo 1 i ne mijenjamo vrijednost prilikom naredne posjete tog istog čvora.

Pomoću sljedeća dva algoritma možemo da obilazimo grafove:

• obilazak po širini
• obilazak po dubini

Obilazak po širini

Algoritam obilazak po širini (eng. breadth-first search BFS) polazi od polaznog čvora, koji smo slučajno odabrali ili proslijedili kao parameter funkcije, posjećuje susjede tog čvora, pa zatim susjede susjeda i tako sve dok svi čvorovi ne budu posjećeni.

Za implementaciju ovog algoritma pogodna je struktura podataka red.

Vrijeme izvršavanja zavisi od načina predstavljanja grafa, ukoliko je to matrica susjedstva vrijeme izvršavanja je O(n²), kod liste susjedstva vrijeme izvršavanja zavisi također i od toga da li je graf usmjeren ili neusmjeren. Usmjeren graf O(e),a kod neusmjerenog grafa O(2e) gdje je u oba slucaja e=d_out(1)+d_out(2)+...+d_out(n).

Obilazak po dubini

Algoritam obilazaka po dubini (eng. depth-first search DFS) polazi od polaznog čvora,koji smo slučajno odabrali ili proslijedili kao parametar funkcije, i ide u jednom pravcu koliko je to moguće. Kada dođe do zadnjeg čvora u jednom pravcu vraća se nazad do prvog čvora koji mu omogućava da ide u dubinu drugog prava i postupak se ponavlja dok svi čvorovi ne budu posjećeni.

Vrijeme izvršavanja je isto kao i kod BFS.

Primjena BFS i DFS

Ova dva algoritma se mogu primjeniti u sljedećim situacijama:

1. određivanje najkraćeg rastojanja u netežinskom grafu
2. provjera cikličnosti grafa
3. određivanje povezanosti komponenti u grafu

Obuhvatna stabla

Obuhvatno stablo

Neka je G=(V,E) neusmjeren i povezan graf. Obuhvatnim stablom grafa G smatramo stablo ST=(U,E') koje ispunjava sljedeća dva uslova:

• ST sadrži sve čvorove grafa G, U=V
• ST sadrži samo odreĎen broj grana iz G, E'⊆ E, potreban da se povežu svi čvorovi međusobno,ali na način da nema ciklusa.

Ako je graf nepovezan a imamo više povezanih komponenti,tada je riječ o obuhvatnoj šumi.

Primjena ovog stabla je česta. Kada je riječ o grafovima primjena ovih stabala se ogleda u sljedećim algoritmima:

• Primov algoritam
• Kruskalov algoritam

Primov algoritam

Primov algoritam (eng.Prim's algorithm) gradi minimalno obuhvatno stablo na sljedeći način:

povezuje dva čvora čija grana trenutno ima najmanju težinu, postupak ponavlja sve dok ne budu povezani svi čvorovi. Prilikom povezivanja čvorova pazi se da se ne napravi ciklus.

Vrijeme izvršavanja zavisi od načina predstavljanja grafa. Vrijeme izvršavanja ako koristimo matricu susjedstva je O(n²), u slučaju implementacije sa listom susjedstva vrijeme izvršavanja je O(e+nlogn).

Kruskalov algoritam

Kruskalov algoritam (end. Kruskal's algorithm) gradi minimalno obuhvatno stablo na sljedeći način:

kreće od prvog čvora u grafu, provjerava sve težine grana koje izlaze iz tog čvora, uzima granu sa najmanjom težinom i spaja polazni čvor sa tim susjedom. Postupak ponavlja sve dok svi čvorovi ne budu povezani i pri tom se pazi da nema ciklusa.

Vrijeme izvršavanja ovog algoritma zavisi od složenosti operacijama sa prioritetnim redom i provjere. Najbolja složenost je O(eloge) gdje je e broj grana u grafu.

Određivanje najkraćeg rastojanja u grafu

Često se kao problem javlja određivanje najkraćeg rastojanja grafa. Posmatrajmo usmjereni težinski graf sa težinama koje odgovaraju grani w(i,j) i neka je težina puta p_1k =(v₁,...,v_k) definisane kao zbir težina grana koje se nalaze na tom putu:

     w(p1k) = $\sum _{i=2}^{k}$ w(vi-1,vi).

Kod ovih algoritama može doći do problema u koliko je neka težina negativna i ako u tom istom grafu postoji ciklus, tada bi mogli upasti u beskonačnu petlju jer tražimo najkraći put tj u ovom slučaju najmanji zbir težina grana.

Sljedeća dva algoritma će nas dovesti do traženog rješenja:

• Dijkstra-ktni algoritam
• Bellman-Ford-ov algoritam

Dijkstra-ktni algoritam

Dijkstra-ktni algoritam (eng. Dijkstra's algorithm) se zasniva na principu održavanja skupa S gdje se pamte do tad posjećeni čvorovi i za koje je nađeno najkraće rastojanje od polaznog čvora. U skupu V-S se nalaze preostali čvorovi. U svakom koraku se jedan čvor iz V-S prebacuje u S.

Na početku se ove procjene stave iz polaznog čvora ukoliko grane postoje na njihovu težinu u suprotnom na ∞ .

Ovaj algoritam radi pod pretpostavkom da su sve težine grana pozitivne.

Bellman-Ford-ov algoritam

Bellman-Ford algoritam (eng. Bellman-Ford algorithm) za razliku od prethodnog može da radi sa negativnim težinama. Prvo provjera da li ima ciklusa i grana sa negativnim težinama, ukoliko nema nalazi najmanje rastojanje od polaznog čvora do svih ostalih čvorova.

Izvori

1. Tomašević, Milo (2008). Algoritmi i strukture podataka. Beograd: Akademska misao. ISBN 9788674663288