DFS, Rekursi & Stack Iteratif
Menjelajah secara mendalam dan menghindari batas rekursi
DFS, Rekursi & Stack Iteratif adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang Dilakukan DFS
DFS menyelam sedalam mungkin melalui satu jalur, lalu mundur dan mencoba jalur berikutnya. Bayangkan menjelajahi lorong labirin satu per satu. 🧭
DFS vs BFS
BFS menyebar dalam lingkaran; DFS menyelam sedalam mungkin terlebih dahulu. Keduanya mengunjungi setiap simpul yang dapat dicapai, tetapi dalam urutan yang sangat berbeda.
Bentuk Rekursif
DFS rekursif menandai sebuah simpul sebagai telah dikunjungi, lalu memanggil dirinya sendiri untuk setiap tetangga yang belum dikunjungi. Tumpukan pemanggilan mengingat tempat untuk kembali.
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)Menandai Sebelum Rekursi
Atur status kunjungan saat memasuki simpul, sebelum menjelajahi tetangganya. Jika tidak, siklus akan membuat DFS mengalami rekursi tak terbatas.
Jebakan Batas Rekursi
Python membatasi rekursi hingga sekitar 1000 pemanggilan. Graf yang dalam memicu RecursionError, yang muncul sebagai hasil kesalahan saat program dijalankan.
Menaikkan Batas
Salah satu perbaikan cepat adalah menaikkan batas dengan setrecursionlimit. Atur nilainya di atas kedalaman terburuk yang mungkin terjadi sebelum menjalankan DFS.
import sys
sys.setrecursionlimit(300000)Gunakan Iterasi Saja
Perbaikan yang paling aman adalah DFS iteratif menggunakan tumpukan Anda sendiri. Tanpa kedalaman pemanggilan, tidak akan ada kegagalan rekursi.
stack = [start]Mengambil dari Tumpukan
Pada setiap langkah, ambil elemen teratas dari tumpukan. Yang masuk terakhir keluar pertama, sehingga DFS menyelam terlebih dahulu ke jalur yang paling baru.
u = stack.pop()Memasukkan Tetangga ke Tumpukan
Setelah mengambil u, masukkan setiap tetangga yang belum dikunjungi ke tumpukan. Tandai mereka agar tidak dimasukkan lagi.
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Perulangan Iteratif Lengkap
Ulangi pengambilan dan pemasukan selama tumpukan masih berisi simpul. Saat tumpukan kosong, setiap simpul yang dapat dicapai telah dikunjungi.
while stack:
u = stack.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Biaya yang Sama seperti BFS
Seperti BFS, DFS mengunjungi setiap simpul dan sisi satu kali, sehingga berjalan dalam O(n + m). Pilih berdasarkan urutan yang paling sesuai dengan tugas.
Pemeriksaan Singkat
DFS rekursif Anda gagal pada graf yang dalam. Mengapa?
Ringkasan
Anda menjalankan DFS secara rekursif atau menggunakan tumpukan sendiri, menandai simpul saat masuk, dan beralih ke versi iteratif ketika graf menjadi dalam. 🎉
Pertanyaan yang Sering Diajukan
Apakah pelajaran “DFS, Rekursi & Stack Iteratif” gratis?
Ya — teks lengkap “DFS, Rekursi & Stack Iteratif” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “DFS, Rekursi & Stack Iteratif”?
Menjelajah secara mendalam dan menghindari batas rekursi Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “DFS, Rekursi & Stack Iteratif” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Adjacency List dari Input
- BFS untuk Jalur Terpendek Tanpa Bobot
- DFS, Rekursi & Stack Iteratif
- Komponen Terhubung & Flood Fill