Grap (uri ng datos)

Sa agham pangkompyuter, ang **grap** ay isang uri ng datos na abstrakt (*abstract data type* o ADT) na binubuo ng set ng mga *node* (tinatawag ding *vertex*) at isang set ng mga *edge* o gilid na nagtatakda ng relasyon (koneksiyon o pagdurugtong) sa pagitan ng mga *node*.  Ang grap na ADT ay nagmumula sa konsepto ng grap sa matematika.

Sa impormal, ang *G=(V,E)* ay binubuo ng mga *berteks*, ang mga elemento ng *V*, na pinagdurugtong ng mga *edge* o gilid, na siyang mga elemento naman ng *E*.  Sa pormal, ang grap, G, ay binibigyang depinisyon na isang nakaayos na pares, *G=(V,E)*, kung saan ang *V* ay isang set (kadalasan ay may hangganan) at ang *E* ay isang set na binubuo ng dalawang elementong subset ng *V*.

## Mga pagpipiliang pagkatawan
Sa pagsasanay, dalawa ang ginagamit na pangunahing istruktura ng datos para sa pagkatawan ng mga grap.  Ang una ay tinatawag na *adjacency* na listahan (o listahan ng magkakatabi), at ipinatutupad sa pamamagitan ng pagkatawan sa bawat *node* bilang isang istruktura ng datos na naglalaman ng listahan ng lahat na adjacent *node* (magkatabing *node*).  Ang pangalawa ay *adjacency* na *matrix*, kung saan ang mga hilig at pangkat ng isang dalawahang-dimensiyong *array* ay kumakatawan sa pinagmulan at destinasyong berteks.  At ang mga tala sa *array* ay nagsasabi kung ang may gilid sa pagitan ng mga berteks.  Ang mga *adjacency* na listahan ay mas pinapaboran sa mga mas kakaunti ang elemento na grap; kundi ay mas maiging gamitin ang *adjacency* na *matrix*.  Panghuli, para sa napakalalaking grap na may regularidad ang pagkakalagay ng mga gilid, maaaring gamitin sa pagkatawan ang isang simbolikong grap.

## Paghahambing sa iba pang balangkas ng datos
Ang mga istruktura ng datos ng grap ay walang herarkiya at samakatuwid ay angkop sa mga set ng datos na ang mga indibidwal na elemento ay magkakadugtong sa masasalimuot na paraan.  Halimbawa, maaaring modelohin ang isang network ng kompyuter sa pamamagitan ng grap.

Ang mga set ng datos na may herarkiya ay maaaring ikatawan sa pamamagitan ng isang binary o di-*binary* na *tree*.  Gayunpaman, dapat ding banggitin na ang mga *tree* ay puwedeng tingnan na isang espesyal na anyo ng grap.

## Mga operasyon
Ang mga algoritmo ng grap ay isang mahalagang larangan ng pag-aaral sa agham kompyuter.  Ang mga tipikal na operasyong may kaugnayan sa mga grap ay:  paghahanap ng path sa pagitan ng dalawang *node*, tulad ng lalim-muna na paghahanap at lawak-muna na paghahanap; at ang paghahanap ng pinakamaigsing daraanan mula sa isang *node* papunta sa isa pa, tulad ng algoritmong Dijkstra.  Ang algoritmong Floyd-Warshall ay masasabing isang solusyon sa paghahanap ng pinakamaigsing daraanan mula sa bawat *node* papunta sa bawat iba pang *node*.

Ang isang may direksiyong grap ay maaaring tingnan na isang daloy ng network (*flow network*), kung saan ang bawat gilid ay may kapasidad at  tumatanggap ng isang daloy.  Ginagamit ang algoritmong Ford-Fulkerson sa paghahanap ng pinakamataas na daloy mula sa isang pinagmulan  patungo sa isang pinaglubugan sa isang grap.

Ang mga grap ay maikakatawan sa dalawang paraan.  Ito ay *adjacency* na *matrix* at *adjacency* na listahan.

Halimbawa, tingnan natin ang sumusunod na grap

              A----------->B
              |            ^
              |            |
              |            |
              V            |
              C ------------
*Adjacency* na *matrix*:

           A B C
        A  0 1 1
        B  0 0 0 
        C  0 1 0

*Adjacency* na listahan

        A  ----> | B | ----> | C | ---- NULL
        B  ----> ---- NULL 
        C  ----> | B | ---- NULL

Kategorya:Estruktura ng datos