Pengertian BFS dan DFS serta penerapannya didalam Game

Depth First Search

DFS (Depth-First-Search) adalah salah satu algoritma penelusuran struktur graf / pohon berdasarkan kedalaman. Simpul ditelusuri dari root kemudian ke salah satu simpul anaknya ( misalnya prioritas penelusuran berdasarkan anak pertama [simpul sebelah kiri] ), maka penelusuran dilakukan terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya hingga mencapai level terdalam.

Jadi, jika ada pohon biner seperti gambar di bawah ini :

Maka, urutan penelusurannya adalah : A – B – D – H – E – I – C – F – G – J – K – L

Breadth First Search

BFS (Breadth First Search) juga merupakan salah satu algoritma penelusuran struktur graf / pohon seperti DFS, namun bedanya BFS melakukan pencarian secara melebar atau per level pohon. Simpul ditelusuri dari root kemudian menelusuri semua simpul pada setiap level di bawahnya ( misalnya prioritas penelusuran dari kiri ke kanan ), maka penelusuran dilakukan terus dari simpul paling kiri ke simpul anak – anak tetangganya yang selevel.

Jadi, untuk pohon biner :

Maka, urutan penelusurannya adalah : A – B – C – D – E – F – G – H – I – J – K – L

Permainan Logika serigala, domba, dan kubis

Diceritakan ada seorang petani yang hendak menyeberangi sungai membawa hasil belanjanya dari pasar, yaitu sekeranjang penuh kubis, juga seekor serigala dan seekor domba. Pemain diminta untuk menyeberangkan petani, serigala, domba, dan keranjang kubis menggunakan sebuah perahu yang hanya muat ditempati oleh dua penumpang. Yang dapat menggunakan perahu hanya sang petani. Permasalahnya adalah pada saat petani tidak ada, serigala akan memakan domba, dan domba akan memakan kubis.

Ini contoh tampilan gamenya

CARA MENYELESAIKAN GAME MENGGUNAKAN DFS

1.  Kondisi awal

2.  Bawa domba ke kiri sungai

3.  Kembali ke kanan

4.  Bawa serigala ke kiri

5.  Kembali ke kanan bersama domba

6.  Bawa kubis ke kiri

7.  Kembali ke kanan

8.  Bawa domba ke kiri (selesai)