Graf (struktura podataka)

Graf sa 6 čvorova i 7 grana.

U računarstvu, graf je vrsta strukture podataka, tačnije apstraktan tip podataka, koji se sastoji od skupa čvorova i skupa grana, koje predstavljaju odnose (veze) između čvorova. Graf kao struktura podataka direktno potiče od matematičkog koncepta grafa.

Graf G se definiše na sledeći način: G=(V,E), gde je V konačan, neprazan skup čvorova, a E je skup grana (veza između čvorova). Kada grane grafa nemaju određen smer, tada graf nazivamo neusmerenim, a u suprotnom je graf usmeren. U praksi, za svaki čvor i granu vezujemo neke podatke sa kojima želimo da manipulišemo.

Izbori reprezentacije

Grafovi se u računarstvu predstavljaju na razne načine. Najčešći su lista povezanosti i matrica povezanosti. Lista povezanosti je implementirana tako što predstavlja svaki čvor kao strukturu podataka koja sadrži listu svih susednih čvorova. Matrica povezanosti je matrica, čije vrste i kolone predstavljaju početne i krajnje čvorove, a dati član matrice predstavlja indikaciju da li između odgovarajuća dva čvora postoji grana (recimo 0 ako ne postoji, a 1 ako postoji). Liste povezanosti se češće koriste kod retkih grafova, a u suprotnom su matrice povezanosti dobar izbor. Takođe, za vrlo velike grafove koji imaju neku pravilnost što se tiče položaja grana, mogući izbor predstavljanja je simbolički graf. Ređe se za predstavljanje grafa koristi matrica incidencije. Vrste ove matrice predstavljaju čvorove, a kolone predstavljaju grane. U svakoj koloni stoje jedinice na mestima koja odgovaraju čvorovima koje spaja odgovarajuća grana (a na ostalim mestima su nule).

Poređenje sa drugim strukturama podataka

Grafovske strukture podataka su ne-hijerarhijske, i stoga su pogodne za podatke gde su pojedinačni elementi povezani na kompleksne načine. Na primer, simulacija računarske mreže se može sprovesti pomoću grafa.

Hijerarhijski skupovi podataka se mogu predstaviti binarnim ili nebinarnim stablom. Stabla se takođe mogu posmatrati i kao grafovi.

Operacije

Grafovski algoritmi su od velikog značaja u računarstvu. Tipične operacije povezane sa grafovima su nalaženje puta između dva čvora, za šta se na primer koriste pretraga grafa u dubinu i pretraga grafa u širinu, i nalaženje najkraćeg puta od jednog do drugog čvora, za šta se može koristiti Dijkstra algoritam.

Vidi još

• Teorija grafova

Spoljašnje veze

• Interaktivne vizuelizacije grafova i drugih struktura podataka.
• NGenerics - implementacija u C#
• Beleške
• Grafovske rutine u Perlu