Struktur Data Graph: Pengertian, Jenis, dan Kegunaannya
Struktur data menyediakan cara dalam menyimpan data agar dapat dikelola dengan mudah, ditangani secara efektif, serta tertata dengan baik.
Adanya berbagai jenis struktur data bertujuan untuk mengelola beberapa jenis data yang berbeda. Biasanya ada data yang perlu penanganan khusus yang tidak dapat disimpan dalam format sederhana.
Kita sebagai seorang yang bergelut di bidang IT dituntut agar memahami berbagai jenis struktur data agar dapat memilih struktur data yang tepat sesuai dengan kasus yang dihadapi.
Nah, di kesempatan ini, kita akan belajar salah satu struktur data yang tak kalah penting, yaitu graph.
Apa itu graph? Kita akan mengulasnya bersama-sama melalui artikel ini.
Graph di atas terdiri atas 4 buah verteks dan 4 pasang sisi atau edge. Dengan verteks disimbolkan sebagai V, edge dilambangkan E, dan graph disimbolkan G, ilustrasi di atas dapat ditulis dalam notasi berikut:
V = {0, 1, 2, 3}
E = {(0,1), (0,2), (0,3), (1,2)}
G = {V, E}
Graph banyak dimanfaatkan untuk menyelesaikan masalah dalam kehidupan nyata, dimana masalah tersebut perlu direpresentasikan atau diimajinasikan seperti sebuah jaringan. Contohnya adalah jejaring sosial (seperti Facebook, Instagram, LinkedIn, dkk)
Pengguna di Facebook dapat dimisalkan sebagai sebuah simpul atau verteks, sementara hubungan pertemanan antara pengguna tersebut dengan pengguna lain direpresentasikan sebagai edge. Tiap tiap verteks dapat berupa struktur yang mengandung informasi seperti id user, nama, gender, dll.
Tidak hanya data pengguna, data apapun yang ada di Facebook adalah sebuah simpul atau verteks.Termasuk foto, album, komentar, event, group, story, dll.
Pengguna dapat mengunggah foto. Ketika telah diunggah, foto akan menjadi bagian dari album. Foto juga dapat dikomentari oleh pengguna lain dan mereka dapat saling berbalas komentar.
Semuanya terhubung satu sama lain, baik dalam bentuk relasi one-to-many, many-to-one, atau many-to-many
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.
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.
Karakteristik Graph
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.
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
Kelebihan Graph
Keunggulan dari struktur data graph adalah sbb:
Dengan menggunakan graph kita dapat dengan mudah menemukan jalur terpendek dan tetangga dari node
Graph digunakan untuk mengimplementasikan algoritma seperti DFS dan BFS.
Graph membantu dalam mengatur data.
Karena strukturnya yang non-linier, membantu dalam memahami masalah yang kompleks dan visualisasinya.
Kekurangan Graph
Adapun kekurangan dari struktur data graph di antaranya
Graph menggunakan banyak pointer yang bisa rumit untuk ditangani.
Memiliki kompleksitas memori yang besar.
Jika graph direpresentasikan dengan adjacency matrix maka edge tidak memungkinkan untuk sejajar dan operasi perkalian graph juga sulit dilakukan.
Penutup
Demikianlah penjelasan lengkap mengenai struktur data graph. Semoga bermanfaat.
Apabila suka dengan artikel seperti ini, Anda bisa mengunjungi rubrik Data Structure atau membaca artikel lainnya mengenai "Struktur Data Tree".
Referensi:
Komentar
Posting Komentar