My first Magazine pemrograman-kompetitif-dasar | Page 110

9 Perkenalan Graf
menemukan shortest path dari suatu node ke seluruh node lainnya. Algoritma 46 menunjukkan
implementasi solusinya.
Algoritma 46 Solusi Perjalanan Tersingkat menggunakan BFS, sambil mencatat kedalaman
pengunjungan suatu node pada array visitTime.
procedure SHORTEST P ATH (A, B)
2:
INITIALIZE Q UEUE ().
3:
visitTime ← new integer[V + 1]
4:
FILL A RRAY (visitTime, −1)
1:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
. Inisialisasi array visitTime dengan -1.
PUSH (A)
visitTime[A] ← 0
while not IS E MPTY Q UEUE () do
curNode ← FRONT ()
POP ()
for ad jNode ∈ ad j(curNode) do
. Jika ad jNode belum pernah dikunjungi...
if visitTime[ad jNode] = −1 then
PUSH (ad jNode)
visitTime[ad jNode] ← visitTime[curNode] + 1
end if
end for
end while
return visitTime[B]
end procedure
Contoh 2
Contoh Soal 9.2: Persebaran Informasi
Bebek-bebek Pak Dengklek merupakan hewan sosial. Apabila seekor bebek mengetahui
suatu informasi, dia akan langsung memberitahu seluruh teman-temannya. Diketahui
terdapat N ekor bebek di peternakan Pak Dengklek, yang dinomori dari 1 sampai dengan N.
Pak Dengklek mengetahui M hubungan pertemanan di antara bebek-bebeknya. Masing-
masing hubungan ini dinyatakan dengan a i dan b i , yang artinya bebek a i berteman dengan
bebek b i . Tentu saja, pertemanan ini berlaku secara dua arah.
Kini Pak Dengklek memiliki sebuah informasi yang ingin ia sampaikan kepada seluruh
bebeknya. Berapa banyak bebek paling sedikit yang Pak Dengklek perlu beritahu tentang
informasi ini, sedemikian sehingga seluruh bebek pada akhirnya akan mengetahui informasi
tersebut?
Pada soal ini, kita dapat menyatakan hubungan pertemanan antar bebek sebagai graf tidak
berarah dan tidak berbobot dengan N node , dan M edge . Bebek ke-i akan menjadi node i, dan
hubungan pertemanan menghubungkan node -node tersebut sebagai edge . Apabila Pak Dengklek
memberi tahu bebek ke-i suatu informasi, banyaknya bebek yang akhirnya akan mengetahui
informasi tersebut sama saja dengan node -node yang dapat dikunjungi dari node i.
Kita dapat menyelesaikan soal ini dengan cara berikut:
100