DFS — Penjelasan Algoritma Depth-First Search

Depth-first search, atau DFS, adalah algoritma untuk menjelajahi tree atau graph dengan mengikuti satu jalur sedalam mungkin sebelum melakukan backtracking. Secara sederhana: DFS terus masuk lebih dalam sampai buntu, lalu kembali ke titik terakhir yang masih memiliki cabang lain.

Jika Anda hanya mengingat satu gagasan, ingat ini: DFS berarti "masuk dalam dulu, lalu backtrack."

Apa yang Dilakukan Depth-First Search

DFS dapat digunakan pada tree maupun graph umum. Mulai dari satu simpul, DFS berulang kali berpindah ke tetangga yang belum dikunjungi. Saat mencapai simpul yang tidak lagi memiliki tetangga yang belum dikunjungi, DFS melakukan backtrack ke simpul sebelumnya dan melanjutkan dari sana.

Perilaku backtracking itulah yang menjadi ciri utama. Pada implementasi rekursif, call stack menanganinya secara otomatis. Pada implementasi iteratif, stack eksplisit menjalankan peran yang sama.

Mengapa Urutan DFS Bisa Berubah

DFS tidak menghasilkan satu urutan kunjungan yang universal. Urutan tepatnya bergantung pada urutan tetangga diperiksa.

Sebagai contoh, jika sebuah simpul memiliki tetangga $B$ dan $C$, mengunjungi $B$ lebih dulu bisa menghasilkan urutan DFS yang berbeda dibanding mengunjungi $C$ lebih dulu. Penelusurannya tetap DFS dalam kedua kasus karena aturannya sama: terus masuk lebih dalam sebelum menjelajahi cabang saudara.

Contoh DFS Pada Graf Kecil

Misalkan graf memiliki koneksi berikut:

• $A$ terhubung ke $B$ dan $C$
• $B$ terhubung ke $D$ dan $E$
• $C$ terhubung ke $F$

Anggap kita selalu memeriksa tetangga dari kiri ke kanan dan mulai dari $A$.

DFS berjalan seperti ini:

1. Kunjungi $A$
2. Pergi ke $B$
3. Pergi ke $D$
4. $D$ tidak punya tetangga yang belum dikunjungi, jadi backtrack ke $B$
5. Dari $B$, pergi ke $E$
6. $E$ selesai, jadi backtrack ke $B$, lalu ke $A$
7. Dari $A$, pergi ke $C$
8. Dari $C$, pergi ke $F$

Jadi salah satu urutan kunjungan DFS yang valid adalah:

$$A, B, D, E, C, F$$

Gagasan utamanya adalah DFS menyelesaikan sisi $A \to B$ sebelum memulai sisi $A \to C$. Jika Anda mengubah urutan tetangga, urutan kunjungannya juga bisa berubah.

Mengapa Backtracking Menggunakan Stack

DFS selalu membutuhkan cara untuk mengingat ke mana harus kembali setelah mencapai jalan buntu. Itulah sebabnya stack muncul secara alami dalam DFS.

Dalam DFS rekursif, setiap pemanggilan fungsi menunggu saat penelusuran masuk lebih dalam, dan program kembali dalam urutan terbalik ketika melakukan backtrack. Dalam DFS iteratif, Anda mendorong simpul ke dalam stack dan mengeluarkannya saat waktunya melanjutkan dari titik terbaru yang belum selesai.

Kompleksitas Waktu dan Ruang DFS

Jika graf disimpan sebagai adjacency list dan setiap simpul ditandai saat pertama kali dikunjungi, DFS berjalan dalam

$$O(V + E)$$

waktu untuk bagian graf yang dapat dijangkau, dengan $V$ adalah jumlah simpul dan $E$ adalah jumlah sisi.

Ruang tambahan biasanya

$$O(V)$$

karena struktur visited dan stack rekursi atau stack eksplisit masing-masing dapat bertambah seiring jumlah simpul.

Kesalahan Umum dalam DFS

Lupa Menandai Simpul yang Sudah Dikunjungi

Pada graph umum, lupa melakukan pengecekan visited dapat membuat DFS terus berputar dalam suatu siklus tanpa akhir. Bahkan pada tree yang disimpan sebagai graph tak berarah, Anda tetap perlu menghindari langsung kembali ke parent kecuali kode Anda menangani kasus itu secara eksplisit.

Menganggap DFS Menemukan Jalur Terpendek

DFS dapat menemukan sebuah jalur, tetapi secara umum tidak menjamin jalur terpendek pada graph tak berbobot. Jika tujuan Anda adalah jalur terpendek dan semua sisi memiliki bobot yang sama, BFS biasanya menjadi pilihan awal yang tepat.

Menganggap Urutan DFS Itu Unik

Urutannya bergantung pada urutan tetangga. Jika urutan itu berubah, urutan penelusurannya juga bisa berubah.

Kapan Depth-First Search Digunakan

DFS berguna ketika Anda ingin menjelajahi struktur, bukan sekadar jarak terdekat terlebih dahulu. Penggunaan umum meliputi:

• memeriksa apakah sebuah simpul dapat dijangkau
• menemukan connected components
• mendeteksi siklus pada beberapa jenis graph
• menelusuri tree
• menyelesaikan masalah bergaya backtracking seperti labirin atau pencarian puzzle

Alasan utama DFS sering muncul adalah karena pola "masuk dalam dulu, lalu backtrack" cocok dengan banyak struktur masalah rekursif.

DFS Vs BFS: Perbedaan Praktisnya

DFS menelusuri satu cabang lebih dulu. BFS menjelajahi semua simpul pada satu jarak sebelum berpindah ke jarak berikutnya.

Jika Anda peduli pada penjelajahan menyeluruh atau struktur rekursif, DFS sering terasa alami. Jika Anda peduli pada jalur terpendek dalam graph tak berbobot, BFS sering menjadi pilihan pertama yang lebih aman.

Coba Penelusuran Serupa

Gambarlah graph kecil dengan enam simpul dan pilih urutan tetangga yang tetap. Jalankan DFS secara manual dan catat dengan tepat kapan Anda maju dan kapan Anda melakukan backtrack. Jika urutannya berubah setelah Anda mengubah urutan tetangga, itu bukan bug. Itu memang bagian dari cara kerja DFS.