Sebelumnya telah kita pelajari berbagai macam jenis struktur data seperti Array, Linked List, dll. Kali ini kita kan mempelajari Struktur Data Graph. 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.
Nah, di kesempatan ini, kita akan belajar salah satu struktur data graph. Apa itu Graph? Mari kita pelajari bersama-sama.
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.
Graph secara matematis dinyatakan sebagai :
G = (V, E)
Dimana
G = Graph
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau Arch
Ciri-ciri graph:
- Sebuah graph mungkin hanya terdiri dari satu simpul
- Sebuah graph belum tentu semua simpulnya terhubung dengan busur
- Sebuah graph mungkin mempunyai simpul yang tak terhubung dengan simpul yang lain
- Sebuah graph mungkin semua simpulnya saling berhubungan
Jenis-jenis Graph
•Graph Berarah (directed graph) : Urutan simpul mempunyai arti. Mis busur AB adalah e1 sedangkan busur BA adalah e8.
•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.
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.
Istilah-istilah pada Graph
- Incident, Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis e=(v,w), maka v dan w disebut “terletak” pada e, dan e disebut incident dengan v dan w.
- Degree (derajat), indegree dan outdegree, Degree sebuah simpul adalah jumlah busur yang incident dengan simpul tersebut.
- Indegree sebuah simpul pada graph berarah adalah jumlah busur yang kepalanya incident dengan simpul tersebut, atau jumlah busur yang “masuk” atau menuju simpul tersebut.
- Outdegree sebuah simpul pada graph berarah adalah jumlah busur yang ekornya incident dengan simpul tersebut, atau jumlah busur yang “keluar” atau berasal dari simpul tersebut.
- Adjacent,
- Pada graph tidah berarah, 2 buah simpul disebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut. Simpul v dan w disebut adjacent.
- Pada graph berarah, simpul v disebut adjacent dengan simpul w bila ada busur dari w ke v.
4. Successor dan Predecessor
Pada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v adalah successor simpul w, dan simpul w adalah predecessor dari simpul v.
5. Path
Sebuah path adalah serangkaian simpul-simpul yang berbeda, yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya.
Perbedaan Graph dengan Tree
- Dalam Graph, edge bebas menghubungkan node-node mana pun.
- Dalam Tree, satu node hanya boleh terhubung ke satu parent dan beberapa child, tidak boleh ke beberapa parent.
- Dalam sebuah Graph bisa dirunut jalur edge yang membentuk jalur putaran dari 1 node kembali ke node semula; ini tidak boleh terjadi dalam Tree.
Spanning Tree
Spanning Tree adalah sebuah Tree yang dibuat dari sebuah Graph dengan menghilangkan beberapa edge-nya. Tree ini harus mengandung semua node yang dimiliki Graph.
Minimum Spanning Tree
- Jika Weighted Graph diubah menjadi Spanning Tree, tiap kombinasi Tree yang dapat dibuat memiliki total weight yang berbeda-beda.
- Problem Minimum Spanning Tree (MST) berusaha mencari Tree seperti apa yang bisa dibuat dari sebuah Weighted Graph dengan total weight seminimal mungkin.
Algoritma Graph
Algoritma Prim-Dijkstra
Ditemukan oleh Robert C. Prim di tahun 1957 dan oleh Edsger Dijkstra di tahun 1959.
Langkah-langkah algoritma Prim-Dijkstra :
- Tentukan node awal, asumsikan semua edge berwarna hitam
- Dari semua edge yang terhubung ke node awal tersebut, pilih edge dengan bobot terkecil
- Tandai edge yang dipilih dengan warna hijau
- Apabila ada edge yang kedua node-nya sudah terkena jalur hijau, tandai edge tersebut dengan warna merah (karena jika dipilih akan membentuk jalur putaran à melanggar syarat tree)
- Tentukan node-node yang berada di jalur hijau sebagai node aktif
- Bandingkan semua edge yang terhubung ke node aktif (hanya edge hitam), pilih yang bobotnya terkecil
- Tandai edge yang dipilih dengan warna hijau
- Ulangi dari langkah ke-4 hingga semua node terlewati jalur hijau
- Ketika semua node telah dilewati jalur hijau, maka jalur hijau yang terbentuk adalah MST yang dicari
Algoritma Kruskal
Ditemukan oleh Joseph Kruskal di tahun 1956.
Langkah-langkah algoritma Kruskal :
- Asumsikan semua edge berwarna hitam
- Bandingkan bobot semua edge hitam, pilih edge dengan bobot terkecil
- Tandai edge yang dipilih dengan warna hijau
- Apabila ada edge yang kedua node-nya sudah terkena jalur hijau, tandai edge tersebut dengan warna merah (karena jika dipilih akan membentuk jalur putaran à melanggar syarat tree)
- Ulangi dari langkah ke-2 hingga semua node terlewati jalur hijau
- Ketika semua node telah dilewati jalur hijau, maka jalur hijau yang terbentuk adalah MST yang dicari
Metode Greedy Shortest Path
Dalam sebuah Graph yang setiap edge yang memiliki weight (bobot), jarak terpendek (shortest path) antara 2 node dapat dicari dengan Metode Greedy. Misal kita hendak mencari jalur terpendek (shortest path) dari node A ke node F, bagaimana cara menghitungnya dengan Metode Greedy?
Langkah-langkah Metode Greedy
- Berangkat dari node awal
- Pilih edge yang memiliki bobot terkecil dari node tersebut
- Maju ke node yang dituju
- Ulangi dari langkah ke-2 hingga mencapai node tujuan
Benarkah solusi yang didaptkan dari Metode Greedy untuk Shortest Path problem adalah benar-benar solusi terbaik? Coba bandingkan solusi berikut :
Metode Greedy menghasilkan solusi yang cukup baik, tapi bukan yang paling baik. Diskusikan mengapa bisa begitu?
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.