depth first search

Depth First Search (DFS): Pengertian dan Cara Kerjanya

Depth First Search pertama kali dipelajari pada abad ke-19 oleh matematikawan Prancis Charles Pierre Trémaux sebagai strategi untuk memecahkan labirin.

Metode ini adalah algoritma rekursif untuk mencari semua simpul dari struktur data pohon atau graph. Untuk menggunakan metode ini kamu harus tahu lebih dahulu apa itu DFS, cara kerjanya dan penerapannya.

Pengertian Depth First Search

Metode Depth First Search atau sering didengar dengan istilah DFS merupakan algoritma pencarian pada sebuah pohon atau tree. Pencarian DFS ini adalah dengan menelusuri satu cabang sebuah pohon sampai ke bawah (menemukan solusi) sebelum melakukan backtracking.

Ilustrasai pencarian dengan DFS dapat kamu lihat pada gambar dibawah, pencarian dimulai dari akar (level 0) dan pencarian dilanjutkan dengan melacak node yang berada paling kanan.

pencarian depth first search

Cara Kerja Depth First Search

Cara kerja metode ini yaitu masukan semua 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.

Kelebihan dan Kekurangan Depth First Search

Depth Firsh Search memiliki kekurangan dan kelebihan diantaranya sebagai berikut.

Kelebihan

  1. Cepat mencapai kedalaman ruang pencarian, jika diketahui bahwa lintasan solusi permasalahan akan panjang maka metode ini tidak akan memboroskan waktu untuk melakukan sejumlah besar keadaan dangkal dalam permasalahan graph.
  2. Lebih efisien untuk ruang pencarian dengan banyak cabang karena tidak perlu mengeksekusi semua simpul pada suatu level terntentu pada daftar open.
  3. Memerlukan memori yang relatif kecil karena banyak node pada lintasan yang aktif saja yang disimpan.
Baca juga :   Node.Js Adalah: Pengertian, Jenis Framework dan Keuntungannya

Kekurangan

  1. Memungkinkan tidak ditemukannya tujuan yang diharapkan dan hanya akan mendapat satu solusi pada setiap pencarian.
  2. Jika pohon yang dibangkitkan mempunyai level dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (tidak complite)
  3. Ketika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (tidak optimal).

Contoh Penerapan Depth First Search

  • Algoritma DFS dapat digunakan untuk menentukan jalur antara dua simpul.
  • Algoritma DFS juga digunakan untuk memecahkan labirin dan teka-teki lainnya hanya dengan satu solusi.
  • DFS digunakan untuk menentukan apakah suatu graph bersifat bipartit atau tidak.
  • Topological sorting, biasa digunakan untuk menjadwalkan pekerjaan dengan ketergantungan yang diberikan di antara pekerjaan.

Kesimpulan

Nah, dari pembelajaran kita di atas dapat kita simpulkan bahwa Depth First Search merupakan algoritma pencarian pada sebuah pohon atau tree. Pencarian pada metode DFS ini adalah dengan menelusuri satu cabang sebuah pohon sampai ke bawah (menemukan solusi) sebelum melakukan backtracking.

Artikel ini merupakan bagian dari seri artikel belajar Kecerdasan Buatan dan jika ada ide topik yang mau kami bahas silahkan komen di bawah ya..