DFS (Depth First Search) : Pengertian, Kekurangan, Kelebihan, dan Contohnya

 

Assalamualaikum Warahmatullahi Wabrokatuh.

Halo teman-teman, bagaimana kabarnya hari ini? Semoga kalian semua berada dalam keadaan sehat walafiyat. Tetap semangat, selalu jaga kesehatan, dan jaga ibadah.

Kali ini kita akan membahas kelanjutan dari materi sebelumnya yaitu BFS. Dan sekarang kita akan belajar mengenai algoritma DFS (Depth First Search). Berikut ini adalah beberapa uraian mengenai algoritma DFS.

DFS (Depth First Search) : Pengertian, Kekurangan, Kelebihan, dan Contohnya

1. Pengertian DFS

    Algoritma Depth First Search adalah algoritma pencarian mendalam yang dimulai dari node awal dilanjutkan dengan hanya mengunjungi node anak paling kiri pada tingkat selanjutnya. 

Gambar 1. DFS dan BFS

   

Cara kerja algoritma Depth First Search yaitu masukan masukan node akar kedalam sebuah tumpukan. Kemudian ambil simpul pertama pada level paling atas, jika simpul merupakan solusi pencarian selesai dan hasil dikembalikan. Jika simpul bukan merupakan solusi, masukan seluruh simpul yang bertetangga dengan simpul tersebut ke dalam tumpukan. Apabila semua simpul sudah dicek dan antrean kosong, pencarian selesai dengan mengembalikan hasil solusi tidak ditemukan. Pencarian diulang dari simpul awal antrean.

2. Kelebihan dan Kekurangan DFS

Kelebihan DFS	Kekurangan DFS
Membutuhkan memori yang relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.	Jika pohon yang dibangkitkan mempunyai level dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete).
Secara kebetulan, metode DFS akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.	Jika terdapat lebih dari 1 solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak Optimal).

3. Contoh Penerapan BFS dalam Studi Kasus

Pencarian jarak terdekat Arad-Bucharest. Berikut ini adalah Peta Rumania.

Gambar 2. Peta Rumania

      Dalam menyelesaikan kasus diatas, kita perlu membuat peta Rumania menjadi gambaran graph yang lebih sederhana. Berikut ini adalah gambaran peta Rumania dalam bentuk graph sederhana:

Gambar 3. Graph Peta Rumania

Penyelesaian dengan DFS:

        Algoritma Depth First Search adalah algoritma pencarian mendalam yang dimulai dari node awal dilanjutkan dengan hanya mengunjungi node anak paling kiri pada tingkat selanjutnya. Dari Gambar 2. Graph Arad-Bucharest, selanjutnya kita dapat membuat Tree untuk melakukan penyelesaian kasus dengan algoritma DFS. Berikut ini adalah gambar tree untuk DFS yang sedikit berbeda dengan tree yang digunakan pada BFS.

Gambar 4. Tree untuk DFS

        Pada tree, tidak semua kota saya tuliskan. Contohnya yaitu kota yang tersambung dari node S dan T secara lengkap. Hal itu dikarenakan target B sudah ditemukan di anak paling kiri, dan pencarian berhenti disana. Sehingga pohon tengah dan pohon kanan tidak akan dilewati. Berikut ini adalah gambaran penyelesaian pencarian kota Bucharest (B) menggunakan algoritma DFS.

Implementasi: Start (A), Goal (B)

Gambar 5. Pencarian Jarak dengan DFS

Penjelasan:

        Pencarian rute dengan DFS, yaitu dengan melakukan pencarian mendalam yang dimulai dari node awal, dilanjutkan dengan hanya mengunjungi node anak paling kiri pada tingkat selanjutnya. Pada tree diatas, rupanya target terletak di anak terdalam paling kiri. Sehingga didapatkan rute berdasarkan algoritma DFS yaitu A Z O S F R. 

       Dari hasil pencarian diatas, maka ditemukan jarak yang dipilih dari Arad ke Bucharest dengan menggunakan algoritma DFS adalah sebagai berikut:

Gambar 6. Hasil Pencarian

Path = A > Z > O > S > F > R
Path-cost = 75 + 71 + 151 + 99 + 211 = 607 KM

Kesimpulan:

    Pada kasus ini, algoritma BFS dengan path-cost 450 KM rupanya lebih efisien dari DFS yang memiliki path-cost 607 KM. Namun pada kasus lainnya, bisa saja algoritma DFS lebih efisien, hal itu tergantung dari kasus itu sendiri.

Itu tadi penjelasan seputar algoritma DFS dan contoh penyelesaian kasus yang pernah saya kerjakan dalam tugas kuliah, sebagai lanjutan postingan sebelumnya. 

Mohon maaf jika ada kekurangan dan kekeliruan. Semoga bermanfaat!

Wassalamualaikum Warahmatullahi Wabarokatuh.