My first Magazine pemrograman-kompetitif-dasar | Page 107

9.5 Penjelajahan Graf
Gambar 9.18: Contoh graf dan urutan penelusurannya dengan DFS. Angka pada node menun-
jukkan urutan node tersebut dikunjungi. Node 1 dikunjungi pertama, node 2
dikunjungi kedua, dan seterusnya). Anak panah menunjukkan pergerakan pe-
ngunjungan node . Edge yang dicetak tebal menyatakan edge yang dilalui oleh
penelusuran secara DFS.
Dalam pemrograman, DFS biasa dilakukan dengan rekursi atau struktur data stack. Untuk
keperluan implementasi, misalkan:
•
•
•
•
Terdapat V node dan E edge .
Setiap node dinomori dari 1 sampai dengan V .
ad j(x) menyatakan himpunan tetangga dari node x.
Terdapat array visited, yang mana visited[x] bernilai true hanya jika x telah dikunjungi.
Contoh implementasi untuk DFS secara rekursif dapat diperhatikan pada Algoritma 43. Imple-
mentasi secara iteratif menggunakan struktur data stack ditunjukkan pada Algoritma 44.
Algoritma 43 Penelusuran graf dengan DFS secara rekursif.
1:
2:
3:
4:
5:
6:
7:
8:
9:
procedure DFS(curNode)
print "mengunjungi curNode"
visited[curNode] ← true
for ad jNode ∈ ad j(curNode) do
if not visited[ad jNode] then
DFS(ad jNode)
end if
end for
end procedure
97