Grapo (kayarian ng datos)

Mula sa Wikipediang Tagalog, ang malayang ensiklopedya
Tumalon sa: nabigasyon, hanapin
May etiketang grapo na may 6 na vertex at 7 edge.

Sa agham pangkompyuter, ang grapo 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 grapo na ADT ay nagmumula sa konsepto ng grapo 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 grapo, 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[baguhin]

Sa praktika, dalawa ang ginagamit na pangunahing istruktura ng datos para sa pagkatawan ng mga grapo. 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 grapo; kundi ay mas maiging gamitin ang adjacency na matrix. Panghuli, para sa napakalalaking grapo na may regularidad ang pagkakalagay ng mga edge, maaaring gamitin sa pagkatawan ang isang simbolikong grapo.

Paghahambing sa iba pang balangkas ng datos[baguhin]

Ang mga istruktura ng datos ng grapo 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 grapo.

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 grapo.

Mga operasyon[baguhin]

Ang mga algoritmo ng grapo ay isang mahalagang larangan ng pag-aaral sa agham kompyuter. Ang mga tipikal na operasyong may kaugnayan sa mga grapo 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) grapo 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 grapoh.

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

Halimbawa, tingnan natin ang sumusunod na grapo

             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