Diskusi dan Kesimpulan Materi BFS dan DFS

Nama : Fat’hiyyah Nuswantari

NPM : 12118579

Kelas : 3KA21

A.    BREADTH FIRST SEARCH (BFS)

Breadth-first search 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 simpul-simpul yang tadi dikunjungi, demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1. Algoritma ini memerluka-n sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpulsimpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungu masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah 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. Urutan proses searching BFS sebagai berikut:

Cara Kerja Algoritma BFS

Berikut langkah-langkah algoritma BFS:

1. Masukkan simpul ujung (akar) ke dalam antrian.

2. Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi.

3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.

4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian.

5. Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan.

6. Ulangi pencarian dari langkah kedua.

A.    DEPTH FIRST SEARCH (DFS)

Depth-first search (DFS) adalah proses searching sistematis buta yang melakukan ekpansi sebuah path (jalur) menuju penyelesaian masalah sebelum melakukan ekplorasi terhadap path yang lain. Proses searching mengikuti sebuah path tunggal sampai menemukan goal atau dead end. Apabila proses searching menemukan dead-end, DFS akan melakukan penelusuran balik ke node terakhir untuk melihat apakah node tersebut memiliki path cabang yang belum dieksplorasi. Apabila cabang ditemukan, DFS akan melakukan cabang tersebut. Apabila sudah tidak ada lagi cabang yang dapat dieksplorasi, DFS akan kembali ke node parent dan melakukan proses searching terhadap cabang yang belum dieksplorasi dari node parent sampai menemukan penyelesaian masalah.

Cara kerja DFS:

Berikut langkah-langkah algoritma DFS:

1.  Masukkan simpul ujung (akar) ke dalam tumpukan

2. Ambil simpul dari tumpukan teratas, lalu cek apakah simpul merupakan solusi

3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan

4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam tumpukan

5. Jika tumpukan kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan

6. Ulangi pencarian dari langkah kedua

Perbandingan penggunaan metode pencarian BFS dan DFS:

Contoh:

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.