Graf (struktura podataka)
U računarstvu je graf vrsta podatkovne strukture kojom se implementira matematički koncept grafa.
Graf se uglavnom sastoji od konačnog (moguće i promjenjivog) skupa uređenih parova koji se nazivaju rubovi ili lukovi (eng. edge), ili od entiteta koji se zovu čvorovi. Kao i u matematici, rub je definiran polaznom i krajnjom točkom, pa kažemo da "pokazuje" ili "ide" od x do y. Čvorovi mogu biti dio strukture grafa ili mogu biti vanjski entiteti predstavljeni pomoću cjelobrojnih indeksa ili referenci.
Osnovne operacije koje omogućava graf G uključuju
adjacent(G, x,y): provjerava postoji li rub od x do y.neighbors(G, x): izlistava sve čvorove y za koje postoji rub od x do y.add(G, x,y): dodaje rub od x do y, ako ne postojidelete(G, x,y): briše rub od x do y, ako postoji
Strukture koje povezuju vrijednosti za rubove su:
get_value(G, x,y): vraća vrijednost vezana za rub (x,y).set_value(G, x,y,v): postavlja vrijednost vezanu za rub (x,y) u v.
Dvije su glavne strukture za reprezentaciju grafova koje se koriste u praksi.
Prva se naziva lista susjedstava (en:adjacency list) i implementira se kao niz s jednom vezanom listom za svaki izvorni čvor, a sadrži destinacijske čvorove rubova koji izlaze iz svakog čvora. Drugi je dvodimenzionalna Booleova matrica susjedstava, koja pokazuje postoji li rub između svakog pojedinog para čvorova. Liste susjedstava su bolji izbor za rijetke (sparse) grafove, dok su za guste grafove (en:dense graphs) bolji izbor matrice susjedstava.
Za grafove koji pokazuju neku pravilnost u položaju rubova, simbolički su grafovi također dobar izbor.