GRAPH DALAM BAHASA PEMROGRAMAN KOMPUTER

 

Graf adalah struktur data yang digunakan untuk merepresentasikan hubungan antara objek-objek. Graf terdiri dari simpul (node) dan tepi (edge) yang menghubungkan simpul-simpul tersebut. 

Untuk Penjelasan lebih jelasnya secara poin pentingnya adalah sebagai berikut :

1. Simpul (Node):

 Simpul adalah titik atau objek dalam graf yang merepresentasikan entitas tertentu.

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.

   Dalam graf sosial, simpul dapat mewakili pengguna media sosial. Dalam graf jalan, simpul bisa menjadi persimpangan atau kota.

2. Tepi (Edge):

    Tepi adalah koneksi atau hubungan antara dua simpul dalam graf.

   Contoh: Jika simpul adalah pengguna media sosial, tepi dapat mewakili koneksi pertemanan antar pengguna. Dalam graf jalan, tepi dapat menggambarkan jalan yang menghubungkan dua tempat.

3. Graf Berarah dan Tidak Berarah:

   Graf berarah memiliki arah pada tepi, artinya koneksi antara dua simpul memiliki orientasi. Graf tidak berarah tidak memiliki arah spesifik pada tepi.

   Contoh: Dalam graf sosial yang berarah, A berteman dengan B tidak sama dengan B berteman dengan A. Dalam graf jalan tidak berarah, jalan dari kota A ke kota B sama dengan dari kota B ke kota A.

4. Graf Berbobot dan Tidak Berbobot:

   Definisi: Graf berbobot memiliki nilai terkait dengan tepi, sementara graf tidak berbobot tidak memiliki nilai tertentu.

   Contoh: Dalam graf berbobot, tepi dapat memiliki bobot yang mewakili jarak, waktu, atau biaya antara simpul-simpul. Dalam graf tidak berbobot, tepi hanya menunjukkan adanya koneksi tanpa nilai tambahan.

5. Siklus (Cycle) dan Graf Acyclic:

   Definisi: Siklus dalam graf adalah rangkaian tepi yang membentuk suatu lingkaran. Graf acyclic tidak memiliki siklus.

   Contoh: Jika Anda dapat bergerak dari simpul A melalui beberapa tepi dan kembali ke A, graf tersebut memiliki siklus. Graf acyclic tidak memiliki kemungkinan untuk kembali ke simpul awal.

6. Contoh Penggunaan Graf:

   Sosial Media: Graf digunakan untuk mewakili jaringan pertemanan di platform sosial.

   Jaringan Transportasi: Graf dapat menggambarkan hubungan jalan, rel kereta, atau penerbangan antar lokasi.

   Sirkuit Elektronik: Dalam teknologi, graf digunakan untuk merepresentasikan sirkuit elektronik.

Jenis-Jenis Graph

Graph dapat dibedakan berdasarkan arah jelajahnya dan ada tidaknya label bobot pada relasinya.

Berdasarkan arah jelajahnya graph dibagi menjadi Undirected graph dan Directed graph.

• Undirected Graph

Pada undirected graph, simpul-simpulnya terhubung dengan edge yang sifatnya dua arah. Misalnya kita punya simpul 1 dan 2 yang saling terhubung, kita bisa menjelajah dari simpul 1 ke simpul 2, begitu juga sebaliknya.

• Directed Graph

Kebalikan dari undirected graph, pada graph jenis ini simpul-simpulnya terhubung oleh edge yang hanya bisa melakukan jelajah satu arah pada simpul yang ditunjuk. Sebagai contoh jika ada simpul A yang terhubung ke simpul B, namun arah panahnya menuju simpul B, maka kita hanya bisa melakukan jelajah (traversing) dari simpul A ke simpul B, dan tidak berlaku sebaliknya.

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.

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

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

Karakteristik Graph

Graph memiliki beberapa karakteristik Diantaranya sebagai berikut:

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

Kelebihan Graph

Kelebihan dari graph diantaranya adalah sebagai berikut :

• Dengan menggunakan graph kita dapat dengan mudah menemukan jalur terpendek dari tetangga dari node
• Graph digunakan untuk mengimplementasikan algoritma seperti DFS dan BFS
• Graph membantu dalam mengatur data.
• Dengan Struktur Graph yang non-linier, graph membantu dalam memahami masalah yang kompleks dan visualisasinya.

Kekurangan Graph

Adapun kekurangan dari graph diantaranya :

• Graph menggunakan banyak pointer yang bisa rumit untuk ditangani
• Memliki kompleksitas memori yang besar.
• Jika graph direpresentasikan dengan adjacency matrix maka edge tidak memungkinkan untuk sejajar dan operasi perkalian graph juga sullit dilakukan.