Penegertian BFS dan DFS
BREADTH FIRST SEARCH (BFS)
Dikenal juga dengan nama algoritma pencarian melebar adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pada aras d+1.
Dikenal juga dengan nama algoritma pencarian melebar adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pada aras d+1.
Algoritma ini memerlukan sebuah
antrian q untuk menyimpan simpul yang telah dikunjungi. Simpul-simpul ini
diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan
dengannya. Tiap simpul yang telah dikunjungi masuk ke dalam antrian hanya satu
kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang
telah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu
kali.Breadth-first search (BFS) melakukan proses searching pada semua node yang
berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan
proses searching pada node di level berikutnya.
DEPTH FIRST SEARCH (DFS)
Dikenal juga pencarian mendalam. dilakukan pada suatu simpul dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada simpul sebelah kanan dan simpul yang kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi.
Dikenal juga pencarian mendalam. dilakukan pada suatu simpul dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada simpul sebelah kanan dan simpul yang kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi.
Pencarian dilakukan pada satu node dalam
setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi
belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node yang
kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak
ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya
sampai ditemukan solusi. Jika solusi ditemukan maka tidak diperlukan proses
backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).
· Berikut contoh beserta perbandingan penggunaan metode pencarian
BFS dan DFS
Contoh :
PENYELESAIAN MENGGUNAKAN
PENCARIAN MELEBAR(BFS) :
Pada BFS teknik pencarian
pesoalannya adalah dengan membuka node (titik) per levelnya.. sehingga pada
persoalan diatas penyelesaian pada BFS adalah.
Urutan node yang di lalui
pada pencarian BFS adalah a,b,c,d,e,f,g,h.
PENYELESAIAN MENGGUNAKAN
PENCARIAN KEBAWAH(DFS) :
Urutan solusi node yang di lalui
pada DFS adalah a,b,e,h.
