My first Magazine pemrograman-kompetitif-dasar | Page 103

9.3 Representasi Graf pada Pemrograman
9.2.2 Directed Acyclic Graph
Directed acyclic graph (DAG) merupakan bentuk khusus dari directed graf, yang tepatnya
bersifat tidak memiliki cycle. Berbeda dengan tree yang mana setiap node harus dapat dikunjungi
dari node lainnya, sifat tersebut tidak berlaku pada DAG.
F
B
C
G
A
D
A
B
E
C
(a)
F
D
E
(b)
Gambar 9.11: Gambar (a) merupakan DAG, sedangkan gambar (b) bukan karena memiliki cycle,
yaitu [B,C, E, D].
9.3
Representasi Graf pada Pemrograman
Dalam pemrograman, dibutuhkan sebuah struktur agar data mengenai graf dapat disimpan
dan diolah secara efisien. Representasi yang akan kita pelajari adalah adjacency matrix , adja-
cency list , dan edge list . Masing-masing representasi ini memiliki keuntungan dan kerugiannya.
Pemilihan representasi mana yang perlu digunakan bergantung dengan masalah yang dihadapi.
9.3.1 Adjacency Matrix
Kita akan menggunakan matriks dengan ukuran V ×V dengan V merupakan banyaknya node .
Misalnya matriks ini bernama matrix.
Pada graf tidak berbobot:
• Jika terdapat edge dari A ke B, maka matrix[A][B] = 1.
• Jika tidak ada, maka matrix[A][B] = 0.
A
D
B
C
A
B
C
D
A
0
1
0
0
B
1
0
0
0
C D
1 1
0 0
0 1
0 0
Gambar 9.12: Graph tidak berbobot beserta adjacency matrix -nya.
Untuk graf berbobot, terdapat sedikit perbedaan:
• Jika terdapat edge dari A ke B dengan bobot w, maka matrix[A][B] = w.
• Jika tidak ada, maka dapat ditulis matrix[A][B] = ∞.
93