Pengertian Graph

 Pengertian Graph

Graph adalah jenis struktur data umum yang susunan datanya tidak berdekatan satu sama lain (non-linier). Graph terdiri dari kumpulan simpul berhingga untuk menyimpan data dan antara dua buah simpul terdapat hubungan saling keterkaitan.

Struktur Data Graph: Pengertian, Jenis, dan Kegunaannya

Simpul pada graph disebut dengan verteks (V), sedangkan sisi yang menghubungkan antar verteks disebut edge (E). Pasangan (x,y) disebut sebagai edge, yang menyatakan bahwa simpul x terhubung ke simpul y.

Fungsi dan Kegunaan Graph

Fungsi dan kegunaan graph di antaranya:

Graph digunakan untuk merepresentasikan aliran komputasi.

Digunakan dalam pemodelan grafik.

Graph dipakai pada sistem operasi untuk alokasi sumber daya.

Google maps menggunakan graph untuk menemukan rute terpendek.

Graph digunakan dalam sistem penerbangan untuk optimasi rute yang efektif.

Pada state-transition diagram, graph digunakan untuk mewakili state dan transisinya.

Di sirkuit, graph dapat digunakan untuk mewakili titik sirkuit sebagai node dan kabel sebagai edge.

Graph digunakan dalam memecahkan teka-teki dengan hanya satu solusi, seperti labirin.

Graph digunakan dalam jaringan komputer untuk aplikasi Peer to peer (P2P).

Umumnya graph dalam bentuk DAG (Directed acyclic graph) digunakan sebagai alternatif blockchain untuk cryptocurrency. Misalnya crypto seperti IOTA

Selain arah jelajahnya, graph dapat dibagi menjadi 2 berdasarkan ada tidaknya label bobot pada koneksinya, yaitu weighted graph dan unweighted graph.

Weighted Graph

Weighted graph adalah jenis graph yang cabangnya diberi label bobot berupa bilangan numerik. Pemberian label bobot pada edge biasanya digunakan untuk memudahkan algoritma dalam menyelesaikan masalah.

Contoh implementasinya misalkan kita ingin menyelesaikan masalah dalam mencari rute terpendek dari lokasi A ke lokasi D, namun kita juga dituntut untuk mempertimbangkan kepadatan lalu lintas, panjang jalan dll. Untuk masalah seperti ini, kita bisa mengasosiasikan sebuah edge e dengan bobot w(e) berupa bilangan ril.

Contoh weighted graph pada struktur data graph

Sumber: baeldung.com

Nilai bobot ini bisa apa saja yang relevan untuk masalah yang dihadapi: misalnya jarak, kepadatan, durasi, biaya, probabilitas, dan sebagainya.

Unweighted Graph

Berbeda dengan jenis sebelumnya, unweighted graph tidak memiliki properti bobot pada koneksinya. Graph ini hanya mempertimbangkan apakah dua node saling terhubung atau tidak.