My first Magazine pemrograman-kompetitif-dasar | Page 104

9 Perkenalan Graf
1
A B C D
A ∞ 3 2 5
B 1 ∞ ∞ ∞
C ∞ ∞ ∞ 8
D ∞ ∞ ∞ ∞
A
3
B
2
5
8
D
C
Gambar 9.13: Graph berbobot beserta adjacency matrix -nya.
Sifat-sifat adjacency matrix adalah:
•
•
•
•
Pada graf tak berarah, adjacency matrix selalu simetris terhadap diagonalnya.
Menambah atau menghapus edge dapat dilakukan dalam O(1).
Memeriksa apakah dua node terhubung dapat dilakukan dalam O(1).
Mendapatkan daftar tetangga dari suatu node dapat dilakukan iterasi O(V ), dengan V
adalah banyaknya node .
Meskipun mudah diimplementasikan, representasi ini cenderung boros dalam penggunaan
memori. Memori yang dibutuhkan selalu O(V 2 ), sehingga tidak dapat digunakan untuk graf
dengan node mencapai ratusan ribu. Jika banyaknya edge jauh lebih sedikit dari O(V 2 ), maka
banyak memori yang terbuang.
9.3.2 Adjacency List
Alternatif lain untuk representasi graf adalah adjacency list .
Untuk setiap node , buat sebuah penampung yang berisi keterangan mengenai tetangganya.
Penampung ini berupa struktur data yang dapat mendukung operasi simpan, cari, dan hapus
data. Pada pembahasan ini, kita akan menggunakan struktur data linier yang telah dipelajari
sebelumnya seperti array atau dynamic array . Untuk graf tidak berbobot, kita cukup menyimpan
node -node tetangga untuk setiap node . Sementara untuk graf berbobot, kita dapat menyimpan
node -node tetangga beserta bobotnya.
A
B
C
D
A
D
B
C
[B,C, D]
[A]
[D]
[]
Gambar 9.14: Graf tidak berbobot beserta adjacency list -nya.
1
B
A
3
2
C
5
8
D
A
B
C
D
[hB, 3i, hC, 2i, hD, 5i]
[hA, 1i]
[hD, 8i]
[]
Gambar 9.15: Graf berbobot beserta adjacency list -nya. Informasi yang disimpan untuk suatu
tetangga adalah pasangan data yang menyatakan node dan bobotnya.
94