My first Magazine pemrograman-kompetitif-dasar | Page 109

9.6 Contoh Permasalahan Graf
Queue ini menyimpan daftar node yang akan dikunjungi. Untuk setiap fase, kunjungi node yang
terdapat di paling depan queue , dan daftarkan seluruh tetangganya yang belum dikunjungi pada
bagian akhir queue . Lakukan hal ini sampai seluruh node terkunjungi. Algoritma 45 menunjukkan
implementasi dari BFS.
Algoritma 45 Penelusuran graf dengan BFS.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
procedure BFS(initialNode)
INITIALIZE Q UEUE ()
PUSH (initialNode)
visited[initialNode] ← true
while not IS E MPTY Q UEUE () do
curNode ← FRONT ()
POP ()
print "mengunjungi curNode"
for ad jNode ∈ ad j(curNode) do
if not visited[ad jNode] then
PUSH (ad jNode)
visited[ad jNode] ← true
end if
end for
end while
end procedure
9.5.3
. Inisialisasi sebuah queue kosong.
. IS E MPTY Q UEUE : bernilai true jika queue kosong.
Analisis Kompleksitas DFS dan BFS
Baik DFS maupun BFS sama-sama mengunjungi setiap node tepat satu kali, dengan meman-
faatkan seluruh edge . Kompleksitas dari kedua metode adalah:
• O(V 2 ), jika digunakan adjacency matrix .
• O(V + E), jika digunakan adjacency list .
9.6
Contoh Permasalahan Graf
Contoh 1
Contoh Soal 9.1: Perjalanan Tersingkat
Di suatu provinsi, terdapat N buah kota. Kota-kota dinomori dari 1 sampai dengan N.
Terdapat E ruas jalan yang masing-masing menghubungkan dua kota berbeda.
Pak Dengklek tinggal di kota A. Suatu hari, beliau ingin pergi ke kota B. Karena sudah tua,
Pak Dengklek ingin melewati sesedikit mungkin ruas jalan untuk sampai ke kota B. Tentukan
berapa banyak ruas jalan tersedikit yang perlu beliau lewati untuk pergi dari kota A ke kota
B!
Permasalahan ini dapat diselesaikan dengan BFS. Karena sifatnya yang menelusuri node
lapis demi lapis, jika suatu node dikunjungi, maka jarak yang ditempuh dari awal sampai node
tersebut pasti jarak terpendek. Hal ini selalu benar untuk segala graf tak berbobot; BFS selalu
99