My first Magazine pemrograman-kompetitif-dasar | Page 108

9 Perkenalan Graf
Algoritma 44 Penelusuran graf dengan DFS secara iteratif menggunakan stack .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
procedure DFS(initialNode)
INITIALIZE S TACK ()
PUSH (initialNode)
visited[initialNode] ← true
while not IS E MPTY S TACK () do
curNode ← TOP ()
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
. Inisialisasi sebuah stack kosong.
. IS E MPTY S TACK : bernilai true jika stack kosong.
Perhatikan baris ke-12 Algoritma 44. Perubahan nilai visited ini akan menjamin suatu node
masuk ke dalam stack paling banyak satu kali.
9.5.2
BFS: Breadth-First Search
Pada BFS, penelusuran node pada graf dilakukan lapis demi lapis. Semakin dekat suatu
node dengan node awal, node tersebut akan dikunjungi terlebih dahulu.
Gambar 9.19: Sebuah graf dan urutan pengunjungan node -nya secara BFS. Angka pada node
menunjukkan urutan node tersebut dikunjungi. Node 1 dikunjungi pertama, node
2 dikunjungi kedua, dan seterusnya). Daerah yang dibatasi garis putus-putus
menyatakan daerah yang mana setiap node memiliki jarak yang sama kepada node
yang dikunjungi pertama. Edge yang dicetak tebal menyatakan edge yang dilalui
oleh penelusuran secara BFS.
Dalam pemrograman, BFS biasa diimplementasikan dengan bantuan struktur data queue .
98