Talangguhit (kayarian ng datos)

Mula sa Tagalog na Wikipedia, ang malayang ensiklopedya

Sa agham pangkompyuter, ang grap o talangguhit ay isang uri ng kayarian ng datos, sa tiyakan ay isang abstraktong uri ng datos (ADT- abstract data type) na binubuo ng set ng mga node (tinatawag ding vertex) at isang set ng mga edge 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 vertex, ang mga elemento ng V, na pinagdurugtong ng mga edge, na siyang mga elemento naman ng E. Sa pormal, ang grap, G, ay binibigyang depinisyon na isang ordered pair, 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 praktika, 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 row (hilig) at column (hanay) ng isang dalawahang-dimensiyong array ay kumakatawan sa source (pinagmulan) at destinasyong vertex. At ang mga tala sa array ay nagsasabi kung ang may edge sa pagitan ng mga vertex. Ang mga adjacency na listahan ay mas pinapaboran sa mga sparse (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 edge, maaaring gamitin sa pagkatawan ang isang simbolikong grap.

Paghahambing sa iba pang istruktura 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 path mula sa isang node papunta sa isa pa, tulad ng algoritmong Dijkstra. Ang Floyd-Warshall algorithm ay masasabing isang solusyon sa paghahanap ng pinakamaigsing path mula sa bawat node papunta sa bawat iba pang node.

Ang isang directed (may direksiyong) grap ay maaaring tingnan na isang network ng daloy (flow network), kung saan ang bawat edge ay may kapasidad at ang bawat edge ay tumatanggap ng isang daloy (flow). Ginagamit ang algoritmong Ford-Fulkerson sa paghahanap ng maksimum na daloy mula sa isang pinagmulan (o hulo) patungo sa isang pinaglubugan (sink, o wawa) sa isang graph.

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