My first Magazine pemrograman-kompetitif-dasar | Page 105

9.3 Representasi Graf pada Pemrograman
Untuk implementasi adjacency list , kita dapat menggunakan struktur data array of dynamic
array . Tiap dynamic array berisi keterangan mengenai tetangga suatu node . Ukuran dari array
merupakan V , yang mana V merupakan banyaknya node . Dengan menggunakan dynamic array ,
banyaknya memori yang digunakan untuk setiap node hanya sebatas banyak tetangganya. Secara
keseluruhan jika graf memiliki E edge , maka total memori yang dibutuhkan adalah O(E).
Jika diimplementasikan dengan array of dynamic array , maka sifat-sifat adjacency list
adalah:
• Kompleksitas menambah edge adalah O(1), dan menghapus adalah O(K) dengan K adalah
banyaknya tetangga dari node yang edge -nya dihapus.
• Memeriksa apakah dua node terhubung oleh edge juga dilakukan dalam O(K).
• Demikian juga untuk mendapatkan daftar tetangga dari node , kompleksitasnya adalah
O(K). Perhatikan bahwa pencarian daftar tetangga ini adalah cara paling efisien yang
mungkin.
9.3.3
Edge List
Pada edge list , seluruh informasi edge disimpan pada sebuah penampung. Penampung ini
berupa struktur data yang juga dapat mendukung operasi simpan, cari, dan hapus data. Untuk
pembahasan kali ini, kita akan menggunakan struktur data array sebagai penampungnya.
Dengan menggunakan array , simpan informasi pasangan node yang terhubung oleh suatu
edge . Pada graf yang berbobot, kita juga perlu menyimpan bobot dari edge yang bersangkutan.
Jelas bahwa memori yang dibutuhkan adalah O(E), dengan E adalah banyaknya edge pada
keseluruhan graf.
A
D
B
C
hA, Bi,
hA,Ci,
hA, Di,
hB, Ai,
hC, Di
Gambar 9.16: Graf tidak berbobot beserta edge list -ya
.
Untuk graf berbobot, kita juga menyimpan bobot dari setiap edge .
1
B
A
3
2
5
8
D
C
hA, B, 3i,
hA,C, 2i,
hA, D, 5i,
hB, A, 1i,
hC, D, 8i
Gambar 9.17: Graf berbobot beserta edge list -ya.
Jika diimplementasikan dengan array , maka sifat-sifat edge list adalah:
• Kompleksitas menambah edge adalah O(1).
95