Grap (uri ng datos)

Isang grap na may tatlong berteks at tatlong gilid.

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