Depth-First Search (DFS)
Masuk ke labirin, terus berjalan sampai menemui jalan buntu, lalu mundur ke percabangan terakhir dan coba jalan berikutnya. Depth-First Search menjelajahi graf dengan cara yang sama. Ini salah satu algoritma graf paling sederhana, dan tumpukan yang dipakainya memberi tahu lebih banyak dari yang Anda kira.
Idenya
Graf adalah sekumpulan simpul yang dihubungkan oleh sisi: ruangan dan pintu, halaman web dan tautan, tugas dan tugas yang menjadi syaratnya. DFS mengunjungi setiap simpul yang bisa dicapainya dari awal, tetapi dengan urutan tertentu: DFS selalu melanjutkan dari simpul yang paling baru dicapainya. DFS menyimpan tumpukan berisi simpul tempat ia berada. Simpul baru masuk ke puncak, dan sebuah simpul baru keluar setelah semua di sekitarnya selesai dijelajahi.
Langkah demi langkah
Masukkan awal ke tumpukan dan beri nomor kunjungan 1. Lihat tetangga berikutnya dari simpul di puncak. Jika belum pernah dilihat, beri nomor kunjungan berikutnya, ingat simpul asalnya, dan masukkan ke puncak tumpukan. Jika sudah pernah dilihat, lewati. Ketika simpul di puncak tidak punya tetangga lagi untuk diperiksa, simpul itu selesai: keluarkan, lalu lanjutkan dengan simpul di bawahnya. Berhenti saat tumpukan kosong, atau saat tujuan tercapai.
Contoh
Ambil graf dengan sisi A–B, A–C, B–D, C–D, C–E, dan D–F, mulai dari A, dan periksa tetangga menurut abjad. Dari A pencarian pergi ke B, dari B ke D, dari D ke C, dan dari C ke E, jadi tumpukannya A, B, D, C, E. Di tengah jalan, C melihat A, yang masih ada di tumpukan: sisi C–A menutup siklus A, B, D, C. E tidak punya tetangga baru, jadi E selesai, lalu C, dan pencarian mundur ke D, yang masih punya F. Urutan kunjungannya A, B, D, C, E, F. Dengan E sebagai tujuan, DFS berhenti dengan jalur A → B → D → C → E, empat sisi, padahal A → C → E hanya perlu dua.
Kegunaannya
Tumpukan selalu merupakan jalur dari awal ke simpul saat ini, sehingga DFS cocok untuk labirin dan teka-teki: itulah ide di balik backtracking. Pada graf tanpa arah, sisi ke simpul yang masih ada di tumpukan menutup siklus. Pada graf berarah, mendaftar simpul dalam urutan kebalikan dari saat simpul selesai memberi urutan topologis, sehingga tiap tugas muncul setelah tugas yang menjadi syaratnya. DFS juga menemukan komponen terhubung, jembatan, dan titik artikulasi, dan versi acaknya adalah cara klasik untuk membuat labirin.
Sejarah
Pada abad ke-19, matematikawan Prancis Charles Pierre Trémaux menjelaskan cara keluar dari labirin apa pun dengan menandai lorong, yaitu DFS yang dilakukan dengan kapur. Pada 1972 dan 1973, Robert Tarjan dan John Hopcroft menunjukkan bahwa DFS memecahkan banyak masalah graf dalam waktu linear, dari komponen terhubung kuat hingga menguji apakah graf bisa digambar tanpa persilangan. Mereka menerima Turing Award 1986 sebagian berkat karya itu.
Jelajahi
Buka aplikasi dan tekan Langkah. Simpul yang tetangganya sedang diperiksa disorot, simpul di tumpukan berwarna biru, dan simpul yang selesai berwarna hijau, masing-masing dengan nomor kunjungannya. Tumpukan ditampilkan di bawah graf, dari awal sampai simpul di puncak. Perhatikan baris status untuk sisi yang menutup siklus, dan pilih tujuan untuk melihat seberapa panjang jalur yang ditemukan dibandingkan dengan BFS.
Pertanyaan yang sering diajukan
Berapa kompleksitas waktu DFS?
O(V + E) untuk V simpul (verteks) dan E sisi: tiap simpul masuk dan keluar tumpukan sekali, dan tiap sisi diperiksa dari kedua ujungnya. DFS butuh memori tambahan O(V) untuk tumpukan dan tanda.
Mengapa DFS memakai tumpukan?
Karena terakhir masuk, pertama keluar membuat pencarian berlanjut dari simpul terbaru dan mundur ke simpul sebelumnya. Rekursi melakukan hal yang sama dengan call stack program. Jika memakai antrean, pencarian akan menyebar lingkaran demi lingkaran: itulah BFS.
Apakah DFS rekursif bermasalah untuk graf besar?
Bisa: jalur panjang berarti rekursi yang dalam, dan banyak bahasa membatasi kedalaman panggilan. Tumpukan eksplisit dalam perulangan menghindari batas itu sambil mengunjungi simpul dengan urutan yang sama.
Di mana DFS dipakai?
Menyelesaikan labirin dan teka-teki dengan backtracking, menemukan siklus, mengurutkan tugas menurut ketergantungannya (pengurutan topologis), menemukan komponen terhubung dan terhubung kuat, membuat labirin, serta di compiler dan build tool yang menelusuri graf ketergantungan.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba Depth-First Search