Pengertian Metode Pencarian BFS dan DFS, beserta Contoh dan Perbandingannya

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.

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.

      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.

 Jadi, sangat mudah bukan membandingkannya, seperti kita lihat perbandingan gambar diatas, BFS melebar melalui titik yang dilalui satu per satu hingga mencapai titik yang dituju, sedangkan DFS lebih simpel, hanya mengarah ke bawah melalui titik yang dilalui langsung menuju ke titik yang dituju.

Sumber :

http://anakkampusgunadarma.blogspot.co.id/2016/11/v-behaviorurldefaultvmlo.html

http://origue.blogspot.co.id/2013/10/blind-search-kecerdasan-buatan.html