GRAPH
DEFINISI
Graph adalah kumpulan noktah (simpul) di dalam bidang dua dimensi yang
dihubungkan dengan sekumpulan garis (sisi).
Representasi visual darigraph adalah dengan menyatakan objek sebagai noktah,
bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan
garis (edge).
G = (V, E)
Dimana :
G = Graph
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau arc
Suatu graph mengandung 2 himpunan, yaitu:
• Himpunan V yang elemennya disebut simpul (atau vertex atau point atau node atau titik).
• Himpunan E yang merupakan pasangan tak urut dari simpul. Anggotanya disebut ruas (edge,
rusuk atau sisi).
Contoh graph :
■ 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 berarah (directed graph) :
Urutan simpul mempunyai arti. Mis busur AB adalah e1 sedangkan busur BA adalah
e8
■ 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
■ Banyaknya simpul disebut : order
■ Banyaknya ruas disebut : size atau ukuran graph
■ Self-loop atau gelung adalah ruas yang kedua titik ujungnya merupakan satu simpul yang
sama.
■ Ruas berganda atau ruas sejajar adalah dua ruas yang mempunyai titik-titik ujung yang
sama atau berujung pada dua simpul yang sama.
ISTILAH-ISTILAH PADA GRAPH
1. 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.
2. 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.
3. 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.
REPRESENTASI GRAPH
Dalam bentuk Matriks :
REPRESENTASI GRAPH
Dalam bentuk Linked-list :
■ Adjency List graph tak berarah
Digambarkan sebagai sebuah simpul yang memiliki 2 pointer.
■ Define struct untuk sebuah simpul yang dapat digunakan sebagai vertex maupun edge.
■ Contoh :
untuk vertex A, memiliki 2 edge yang terhubung yaitu e1 dan e2
.
■ Gambar di atas dapat disusun dengan lebih sederhana, sbb :
■ Adjency List graph berarah
■ Graph berarah dan berbobot
Penyelesaian kasus Graph halaman sebelumnya :
• Mendefinisikan simpul untuk vertex dan edge
• Mengidentifikasi Simpul pertama sebagai vertex yang pertama
• Menambahkan vertex sisanya
• Menambahkan edge pada masing-masing vertex yang telah terbentuk
• Tampilkan representasi graph berikut bobotnya