H. STRUKTUR DATA : GRAPH

Graph adalah kumpulan node (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan obyek-obyek diskrit dan hubungannya. Graph merupakan suatu cabang ilmu yang memiliki banyak terapan, salah satunya pada sistem komputer yang dikenal dengan struktur data graph.

• PENGERTIAN

Dalam bidang ilmu komputer, sebuah graph dapat dinyatakan sebagai sebuah struktur data, atau secara spesifik dinamakan sebagai ADT (abstract data type) yang terdiri dari kumpulan simpul dan sisi yang membangun hubungan antarsimpul. Struktur data graph adalah bentuk implementasi dari teori graf yang mencakup definisi, dan hukum-hukum yang menyertainya, di mana struktur data ini berbentuk network atau jaringan, yang hubungan antarelemennya adalah many-to-many.

Struktur data ini bergantung pada struktur graph dan algoritma yang digunakan untuk memanipulasi graph, di mana keterhubungannya tak terbatas antara entitas data. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straight forward) dilakukan pada strukturnya sendiri. Contoh penerapan struktur data graph adalah Informasi topologi jaringan dan keterhubungan antarkota-kota.

• KEGUNAAN

Pemakaian struktur data yang tepat di dalam proses pemrograman, akan menghasilkan algoritma yang jelas dan tepat sehingga menjadikan program secara keseluruhan lebih sederhana.

Adapun kegunaan dari struktur data graph di antaranya:

• Graph digunakan untuk merepresentasikan aliran komputasi.
• Digunakan dalam membuat pemodelan grafik.
• Graph dipakai pada sistem operasi untuk alokasi sumber daya.
• Pada Google maps graph digunakan untuk menemukan rute terpendek.
• Pada state-transition diagram, graph digunakan untuk mewakili state dan transisinya.
• Graph digunakan dalam memecahkan teka-teki dengan hanya satu solusi, seperti labirin.
• Graph digunakan dalam jaringan komputer untuk aplikasi Peer to peer (P2P).

• KARAKTERISTIK

Graph memiliki beberapa karakteristik sebagai berikut:

• Jarak maksimum dari sebuah simpul ke semua simpul lainnya dianggap sebagai eksentrisitas dari simpul tersebut.
• Titik yang memiliki eksentrisitas minimum dianggap sebagai titik pusat dari graph.
• Nilai eksentrisitas minimum dari semua simpul dianggap sebagai jari-jari dari graph terhubung.

• JENIS JENIS

1. Graph Berarah (directed graph) : Urutan simpul mempunyai arti. Mis busur AB adalah e1 sedangkan busur BA adalah e8.

2. Graph Tak Berarah (undirected graph atau non-directed graph) : Urutan simpul dalam sebuah busur tidak dipentingkan. Mis busur e1 dapat disebut busur AB atau BA.

3. Graph Berbobot (Weighted Graph)

• Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot.
• Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.