My first Magazine pemrograman-kompetitif-dasar | Page 106

9 Perkenalan Graf
• Kompleksitas menghapus edge dan memeriksa keterhubungan sepasang node adalah
O(E).
• Demikian juga untuk mendapatkan daftar tetangga dari node , kompleksitasnya adalah
O(E).
9.4
Perbandingan Representasi Graf
Tabel 9.1 menunjukkan ringkasan operasi dan kompleksitas pada graf dengan V node dan E
edge untuk berbagai representasi, dengan K adalah banyaknya node yang bertetangga dengan
node yang sedang kita periksa.
Tabel 9.1: Tabel perbandingan operasi dan kompleksitas berbagai representasi graf, dengan
catatan adjacency list diimplementasikan dengan array of dynamic array dan edge
list diimplementasikan dengan array .
Adj.Matrix Adj.List Edge List
Tambah edge
O(1)
O(1)
O(1)
Hapus edge
O(1)
O(K)
O(E)
Cek keterhubungan
O(1)
O(K)
O(E)
Daftar tetangga
O(V )
O(K)
O(E)
2
Kebutuhan memori
O(V )
O(E)
O(E)
Kompleksitas operasi-operasi adjacency list dan edge list yang ditunjukkan Tabel 9.1 bisa
jadi lebih efisien, apabila kita menggunakan struktur data yang lebih efisien dalam penampungan
datanya. Sebagai contoh, struktur data balanced binary search tree yang digunakan sebagai
penampungan dapat melakukan operasi simpan, cari, dan hapus dalam kompleksitas logaritmik.
Struktur data lanjutan seperti balanced binary search tree tidak dibahas pada buku ini. Pembaca
yang tertarik dapat mempelajarinya pada buku Introduction to Algorithm. 13
9.5
Penjelajahan Graf
Penjelajahan graf merupakan penelusuran node -node pada suatu graf menurut suatu
aturan tertentu. Terdapat 2 metode yang dapat digunakan, yaitu DFS dan BFS.
9.5.1
DFS: Depth-First Search
Penelusuran dilakukan dengan mengutamakan node yang lebih dalam terlebih dahulu (depth-
first ). Misalkan penelusuran secara DFS dimulai dari suatu node . Selama masih terdapat
tetangga yang belum dikunjungi, kunjungi tetangga tersebut. Pada node tetangga ini, lakukan
pula hal yang serupa. Ketika kita mencapai suatu node yang mana seluruh tetangganya sudah
pernah dikunjungi, kembali ke node terakhir yang dikunjungi tepat sebelum node ini dikunjungi.
Sebagai contoh, perhatikan Gambar 9.18. Penelusuran akan dilakukan menuju node yang paling
dalam, lalu keluar, dan ke node lain yang paling dalam, dan seterusnya.
96