Algoritma DFS dan BFS

Algoritma Graph

Algoritma Traversal di dalam graf berarti mengunjungi
simpul-simpul dengan cara yang sistematik.

• Algoritma traversal di dalam graf:
1. BFS: Pencarian Melebar (Breadth First Search),
2. DFS: Pencarian Mendalam (Depth First Search)

Algoritma Pencarian Melebar (BFS)

• Traversal dimulai dari simpul v.
• Algoritma:

1. Kunjungi simpul v,
2. Kunjungi semua simpul yang bertetangga
dengan simpul v terlebih dahulu.
3. Kunjungi simpul yang belum dikunjungi dan
bertetangga dengan simpul-simpul yang tadi
dikunjungi, demikian seterusnya.

Metode Pencarian Mendalam (DFS)

• Traversal dimulai dari simpul v.
• Algoritma:

1. Kunjungi simpul v,
2. Kunjungi simpul w yang bertetangga dengan
simpul v.
3. Ulangi DFS mulai dari simpul w.

4. Ketika mencapai simpul u sedemikian sehingga
semua simpul yang bertetangga dengannya telah
dikunjungi, pencarian dirunut-balik (backtrack)
ke simpul terakhir yang dikunjungi sebelumnya
dan mempunyai simpul w yang belum
dikunjungi.
5. Pencarian berakhir bila tidak ada lagi simpul
yang belum dikunjungi yang dapat dicapai dari
simpul yang telah dikunjungi.

 Sekian ^^