Mengenal DFS (Depth First Search): Apa Itu dan Bagaimana Cara Kerjanya?

Table of Contents

Depth-First Search (DFS) adalah salah satu algoritma dasar yang sering banget dipakai dalam dunia computer science dan pemrograman, terutama saat kita berurusan dengan struktur data yang terhubung seperti graf (graph) dan pohon (tree). Kalau diterjemahkan secara harfiah, namanya “Pencarian Prioritas Kedalaman”. Sesuai namanya, cara kerja algoritma ini memang unik: dia akan mencoba menjelajahi setiap “cabang” atau “jalur” sedalam mungkin sebelum akhirnya kembali (backtrack) dan mencoba jalur lain.

Apa Itu Depth-First Search (DFS)?¶

Secara singkat, DFS adalah algoritma penelusuran (traversal) atau pencarian (search) yang menjelajahi graph atau tree. Bayangkan kamu sedang berada di labirin dan ingin menemukan jalan keluar. Strategi DFS ini mirip dengan cara kamu masuk ke satu lorong, terus berjalan sampai mentok di tembok atau jalan buntu, baru kemudian mundur sedikit untuk mencoba lorong lain yang belum dijelajahi dari persimpangan terakhirmu. Algoritma ini tidak menjamin menemukan jalur terpendek, tapi sangat efektif untuk banyak tugas lain.

Prinsip utamanya adalah mengunjungi sebuah node, lalu segera mengunjungi salah satu tetangganya yang belum dikunjungi, dan terus menyelam ke dalam sampai tidak ada lagi node yang bisa dikunjungi di jalur tersebut. Begitu mentok, barulah algoritma “mundur” (backtrack) ke node sebelumnya yang masih punya tetangga belum dikunjungi dan mencoba jalur dari sana.

Image just for illustration

Bagaimana Cara Kerja DFS?¶

Mekanisme kerja DFS bisa dibilang cukup intuitif, meskipun implementasinya butuh pemahaman soal stack (tumpukan) atau rekursi. Mari kita bedah langkah demi langkahnya:

1. Mulai dari Node Awal: Pilih satu node di graf atau pohon sebagai titik awal penjelajahanmu. Node ini biasanya disebut sebagai starting node atau root (untuk pohon).
2. Kunjungi Node Awal: Tandai node awal sebagai “sudah dikunjungi” (visited). Ini penting agar kita tidak berputar-putar di tempat yang sama atau masuk ke dalam infinite loop pada graf yang punya siklus.
3. Jelajahi Tetangga: Dari node yang sedang dikunjungi, cari salah satu tetangganya yang belum dikunjungi.
4. Masuk Lebih Dalam: Jika ada tetangga yang belum dikunjungi, segera pindah ke tetangga tersebut, tandai dia sebagai “sudah dikunjungi”, dan ulangi langkah 3 dari node yang baru saja dikunjungi itu. Algoritma ini akan terus “menyelam” ke dalam jalur ini sejauh mungkin.
5. Backtrack: Jika dari node yang sedang dikunjungi sudah tidak ada lagi tetangga yang belum dikunjungi (artinya, semua tetangganya sudah dikunjungi atau node tersebut memang tidak punya tetangga), maka algoritma akan “mundur” (backtrack) ke node sebelumnya di jalur yang sama.
6. Lanjutkan dari Node Sebelumnya: Dari node tempatmu mundur, cari lagi apakah ada tetangga lain yang belum dikunjungi (selain yang tadi membawamu ke jalur buntu). Jika ada, ulangi langkah 4 dari sana. Jika tidak ada lagi, mundur lagi.
7. Berhenti: Proses ini berlanjut sampai semua node yang terhubung dengan node awal telah dikunjungi. Jika grafnya tidak terhubung (disconnected), mungkin kamu perlu memilih node awal lain di komponen yang berbeda dan mengulang prosesnya untuk mengunjungi semua node.

Konsep “Depth First”¶

Nama “Depth-First” berasal dari strategi penjelajahannya. Algoritma ini memprioritaskan kedalaman (depth) suatu jalur daripada mejelajahi semua tetangga di level yang sama (breadth). Bandingkan dengan Breadth-First Search (BFS) yang justru menjelajahi semua tetangga terdekat terlebih dahulu, baru kemudian tetangga dari tetangga tersebut, dan seterusnya level demi level. DFS itu seperti menyusuri satu lorong sempit panjang sampai ujung, baru kemudian mencoba lorong sempit panjang lainnya.

Peran Stack dalam DFS¶

Implementasi DFS secara alami menggunakan struktur data stack (tumpukan). Saat kita pindah dari satu node ke tetangganya, node yang baru saja kita tinggalkan (node asal) itu “ditumpuk” sementara. Ketika kita mencapai jalan buntu dan perlu mundur (backtrack), kita mengambil node yang paling atas dari tumpukan (yaitu node yang terakhir kali kita singgahi sebelum pindah ke jalur buntu) dan melanjutkan penjelajahan dari sana. Implementasi rekursif DFS menggunakan call stack internal dari sistem, sementara implementasi iteratif biasanya menggunakan stack eksplisit yang kita kelola sendiri.

Aplikasi Depth-First Search (DFS)¶

Meskipun tidak selalu cocok untuk mencari jalur terpendek, DFS punya banyak kegunaan penting dalam berbagai masalah computer science. Ini beberapa contohnya:

1. Penelusuran Graf dan Pohon (Graph and Tree Traversal)¶

Ini adalah aplikasi yang paling mendasar. DFS bisa digunakan untuk mengunjungi setiap node dalam sebuah graf atau pohon yang terhubung. Ini berguna misalnya untuk mencetak semua elemen dalam pohon, mengecek apakah suatu node bisa dijangkau dari node lain, atau sekadar memastikan tidak ada node yang terisolasi.

2. Mencari Komponen Terhubung (Finding Connected Components)¶

Pada graf yang tidak terhubung (disconnected), DFS bisa digunakan untuk menemukan semua komponen yang saling terhubung. Caranya, mulai DFS dari node arbitrer. Semua node yang dikunjungi dalam satu kali penelusuran DFS (sebelum algoritma berhenti karena tidak ada node terhubung lain) merupakan satu komponen terhubung. Ulangi proses ini dari node yang belum dikunjungi sama sekali (jika ada) untuk menemukan komponen terhubung lainnya.

3. Pengurutan Topologi (Topological Sorting)¶

Ini adalah pengurutan node dalam graf berarah (directed graph) tanpa siklus (Directed Acyclic Graph - DAG) sedemikian rupa sehingga untuk setiap edge dari node A ke node B, node A selalu muncul sebelum node B dalam urutan. Pengurutan topologi sangat berguna untuk menjadwalkan tugas yang memiliki dependensi (misalnya, tugas A harus selesai sebelum tugas B bisa dimulai). DFS bisa digunakan untuk menghasilkan pengurutan topologi secara efisien.

4. Mendeteksi Siklus (Cycle Detection)¶

DFS adalah alat yang ampuh untuk mendeteksi adanya siklus dalam graf berarah maupun tak berarah. Pada graf tak berarah, siklus terdeteksi jika saat menjelajahi dari node U ke tetangga V, V sudah dikunjungi dan V bukan node asal kita (parent dari U) dalam penelusuran DFS saat ini. Pada graf berarah, siklus terdeteksi jika saat menjelajahi dari U ke V, V sudah dikunjungi dan V masih berada dalam current recursion stack (artinya, V adalah salah satu “nenek moyang” U dalam penelusuran jalur saat ini).

5. Menyelesaikan Puzzle dan Labirin (Solving Puzzles and Mazes)¶

Karena sifatnya yang menyelam ke dalam jalur, DFS sangat alami untuk digunakan dalam masalah-masalah seperti keluar dari labirin atau menyelesaikan puzzle yang bisa direpresentasikan sebagai graf, di mana setiap keadaan (state) puzzle adalah node dan setiap kemungkinan langkah adalah edge. Algoritma ini akan mencoba satu urutan langkah sampai selesai atau buntu.

6. Pencarian Jalur (Pathfinding)¶

Meskipun tidak menjamin jalur terpendek (kecuali pada pohon atau graf tanpa bobot jika kita mencari any path, bukan shortest), DFS bisa digunakan untuk mencari sebuah jalur antara dua node. Misalnya, “apakah ada jalan dari node A ke node B?”. DFS bisa menjawabnya dengan mencoba menelusuri dari A dan melihat apakah B bisa dijangkau.

7. Mencari Jembatan dan Titik Artikulasi (Finding Bridges and Articulation Points)¶

Ini adalah aplikasi yang sedikit lebih lanjut. Jembatan adalah edge yang jika dihapus akan meningkatkan jumlah komponen terhubung pada graf. Titik artikulasi adalah node yang jika dihapus beserta semua edge yang terhubung padanya juga akan meningkatkan jumlah komponen terhubung. DFS, dengan beberapa modifikasi dan pencatatan tambahan (seperti waktu masuk dan waktu terendah yang bisa dijangkau), bisa digunakan untuk menemukan struktur kritis ini dalam graf.

DFS vs. BFS: Kapan Memilih yang Mana?¶

Seringkali DFS dibandingkan dengan saudaranya, Breadth-First Search (BFS). Keduanya sama-sama algoritma traversal, tapi cara kerjanya beda drastis dan cocok untuk masalah yang berbeda.

• BFS menjelajahi level per level. Dia mengunjungi semua tetangga terdekat, lalu semua tetangga dari tetangga terdekat, dan seterusnya. BFS menggunakan queue (antrean) dan sangat cocok untuk mencari jalur terpendek pada graf tanpa bobot (unweighted graph).
• DFS menyelam sedalam mungkin di satu jalur sebelum backtrack. Dia menggunakan stack (atau rekursi) dan lebih cocok untuk tugas-tugas seperti mendeteksi siklus, pengurutan topologi, dan masalah yang membutuhkan penelusuran hingga ke ujung cabang seperti menyelesaikan labirin.

Pilihan antara DFS dan BFS juga bisa bergantung pada bentuk grafnya. Jika grafnya sangat “tinggi” dan “kurus” (deep and narrow), DFS mungkin lebih efisien dalam hal memori. Tapi jika grafnya sangat “lebar” dan “datar” (wide and shallow), BFS mungkin lebih cepat menemukan tujuannya jika tujuan tersebut berada di dekat node awal.

Kelebihan dan Kekurangan DFS¶

Seperti algoritma lainnya, DFS punya sisi positif dan negatif:

Kelebihan:¶

• Efisiensi Memori: Pada graf atau pohon yang sangat “tinggi” dan “kurus”, DFS seringkali membutuhkan memori yang jauh lebih sedikit dibandingkan BFS. Ini karena stack DFS hanya menyimpan jalur saat ini, sedangkan queue BFS bisa menyimpan semua node di level saat ini.
• Menemukan Solusi dengan Cepat (jika ada di jalur dalam): Jika solusi atau target yang dicari berada jauh di dalam satu cabang yang ditelusuri pertama kali, DFS bisa menemukannya lebih cepat daripada BFS.
• Mudah Diimplementasikan (terutama rekursif): Implementasi DFS secara rekursif seringkali terlihat lebih ringkas dan mudah dipahami, terutama untuk masalah penelusuran pohon.
• Berguna untuk Tugas Spesifik: Sangat efektif untuk mendeteksi siklus, pengurutan topologi, dan masalah yang membutuhkan penjelajahan hingga ujung cabang seperti pemecahan labirin.

Kekurangan:¶

• Tidak Menjamin Jalur Terpendek: DFS tidak menemukan jalur terpendek antara dua node pada graf berbobot atau bahkan pada graf tanpa bobot (kecuali dalam skenario yang sangat spesifik). BFS lebih unggul dalam hal ini.
• Bisa Terjebak: Pada graf tak berarah dengan siklus atau graf berarah, tanpa mekanisme penanda “visited”, DFS bisa masuk ke dalam infinite loop. Bahkan dengan penanda “visited”, pada graf yang sangat dalam dan tak terbatas (secara konseptual), DFS bisa terus menjelajahi satu jalur tanpa pernah mencapai node lain atau solusi.
• Memori Bisa Besar pada Graf Lebar: Jika grafnya sangat “lebar” (punya banyak tetangga di setiap node) dan menggunakan implementasi rekursif, call stack bisa menjadi sangat besar dan berpotensi menyebabkan stack overflow.

Tips Memahami dan Menggunakan DFS¶

1. Gambarkan Grafnya: Untuk pemahaman awal, coba gambarkan graf atau pohon yang akan ditelusuri dan secara manual ikuti langkah-langkah DFS, tandai node mana yang sudah dikunjungi dan urutan penelusurannya.
2. Pahami Peran Stack/Rekursi: Sadari bahwa inti dari “backtracking” DFS adalah penggunaan stack (baik implisit lewat rekursi atau eksplisit). Node yang terakhir kali dikunjungi sebelum pindah ke tetangga adalah node pertama yang akan “dipertimbangkan” kembali saat backtrack.
3. Perhatikan Kondisi “Visited”: Selalu pastikan ada mekanisme untuk menandai node yang sudah dikunjungi agar tidak terjebak dalam siklus atau mengunjungi node yang sama berulang kali.
4. Pilih Implementasi yang Tepat: Untuk pemahaman konsep, rekursif lebih intuitif. Tapi untuk menghindari potensi stack overflow pada graf sangat dalam atau ketika kontrol yang lebih low-level dibutuhkan, implementasi iteratif dengan stack eksplisit lebih disarankan.

Fakta Menarik tentang DFS¶

• DFS pertama kali dijelaskan oleh seorang matematikawan Prancis bernama Charles Pierre Trémaux sebagai strategi untuk menyelesaikan labirin pada abad ke-19, jauh sebelum era komputer digital!
• DFS adalah dasar dari banyak algoritma graf yang lebih kompleks, seperti algoritma Tarjan untuk mencari komponen terhubung kuat (strongly connected components) atau algoritma Kosaraju.
• Dalam kecerdasan buatan (AI), DFS sering digunakan dalam algoritma pencarian state space untuk menemukan solusi masalah, misalnya dalam permainan catur atau puzzle lainnya, meskipun varian seperti Iterative Deepening DFS (IDDFS) lebih umum digunakan karena menggabungkan kelebihan memori DFS dan jaminan kelengkapan (completeness) BFS (menemukan solusi jika ada di kedalaman tertentu).

Secara umum, DFS adalah algoritma serbaguna dan fundamental yang setiap programmer harus pahami. Kemampuannya untuk menjelajahi kedalaman membuatnya cocok untuk banyak masalah yang melibatkan struktur data terhubung, meskipun bukan pilihan utama jika tujuan utamanya adalah mencari jalur terpendek.

DFS benar-benar alat yang ampuh di kotak perkakas seorang developer, membuka pintu ke pemahaman algoritma graf yang lebih kompleks dan membantu memecahkan berbagai macam masalah komputasi.

Sudahkah kamu pernah menggunakan DFS dalam proyek atau latihan coding-mu? Atau mungkin ada aplikasi DFS lain yang menarik yang kamu ketahui? Yuk, bagikan pengalaman dan pendapatmu di kolom komentar di bawah!