Depth First Search (DFS) merupakan salah satu algoritma pencarian yang paling fundamental dalam ilmu komputer, khususnya pada struktur data seperti tree dan graph. Algoritma ini pertama kali diperkenalkan oleh Charles Pierre Trémaux pada abad ke-19 saat mencoba menemukan cara efektif untuk menyelesaikan labirin. Hingga saat ini, konsep DFS masih banyak digunakan dalam berbagai aplikasi seperti pencarian jalur, analisis graph, hingga kecerdasan buatan.
Seiring penggunaannya yang luas, banyak yang mulai bertanya apa itu Depth First Search, bagaimana cara kerjanya, dan kapan algoritma ini digunakan dalam pemrograman. Memahami DFS sangat penting karena algoritma ini menjadi dasar bagi banyak teknik pencarian lainnya. Oleh karena itu, pada artikel ini kita akan membahas secara lengkap mulai dari pengertian, cara kerja, kelebihan dan kekurangan, hingga contoh penerapan Depth First Search.
Apa Itu Depth First Search?
Depth First Search (DFS) adalah algoritma pencarian yang digunakan untuk menelusuri struktur data seperti tree (pohon) dan graph (graf) dengan cara menjelajahi satu cabang hingga mencapai titik terdalam sebelum kembali (backtracking) untuk menjelajahi cabang lainnya.
Berbeda dengan algoritma pencarian lain seperti Breadth First Search (BFS), DFS lebih memprioritaskan kedalaman daripada lebar. Artinya, algoritma ini akan terus bergerak ke node berikutnya sampai tidak ada lagi node yang bisa dikunjungi, baru kemudian kembali ke node sebelumnya untuk melanjutkan pencarian.
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.
Baca Juga: Algoritma Backtracking: Cara Kerja dan Implementasinya
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.
Baca Juga: Algoritma Rekursif: Pengertian, Konsep, Jenis dan Kelebihan
Kelebihan dan Kekurangan Depth First Search
Depth Firsh Search memiliki kekurangan dan kelebihan diantaranya sebagai berikut.
Kelebihan Depth First Search
- 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.
- Lebih efisien untuk ruang pencarian dengan banyak cabang karena tidak perlu mengeksekusi semua simpul pada suatu level terntentu pada daftar open.
- Memerlukan memori yang relatif kecil karena banyak node pada lintasan yang aktif saja yang disimpan.
Kekurangan Depth First Search
- Memungkinkan tidak ditemukannya tujuan yang diharapkan dan hanya akan mendapat satu solusi pada setiap pencarian.
- Jika pohon yang dibangkitkan mempunyai level dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (tidak complite)
- 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).
Baca Juga: Belajar Decision Tree: Pengertian, Konsep, Penerapan dan Cara Kerjanya
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.
Baca Juga: Breadth First Search: Cara Kerja, Contoh dan Kode Program
Kesimpulan
Pada pembelajaran kita di atas dapat kita simpulkan bahwa Depth First Search (DFS) merupakan salah satu algoritma pencarian yang digunakan untuk menelusuri struktur data seperti tree dan graph dengan pendekatan kedalaman terlebih dahulu. Dengan cara kerja yang fokus pada satu cabang hingga mencapai titik terdalam, DFS menjadi solusi yang efisien dalam berbagai kasus pencarian.
Memahami pengertian depth first search, cara kerja, serta kelebihan dan kekurangannya sangat penting dalam pengembangan algoritma dan struktur data. Dengan penerapan yang tepat, DFS dapat digunakan dalam berbagai bidang seperti pencarian jalur, analisis graph, hingga pemecahan masalah kompleks seperti labirin.
Artikel ini merupakan bagian dari seri Kecerdasan Buatan KantinIT.com. Jika artikel ini bermanfaat, jangan lupa bagikan ke media sosial atau ke teman kamu.
