DFS, Özyineleme ve Yinelemeli Yığınlar
Derinlemesine keşfedin ve özyineleme sınırlarından kaçının.
DFS, Özyineleme ve Yinelemeli Yığınlar, CoddyKit'te ücretsiz bir Competitive Programming Academy dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, Competitive Programming Academy öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
DFS Ne Yapar
DFS bir yol boyunca gidebildiği kadar derine iner, sonra geri dönüp sıradakini dener. Bir labirentte koridorları tek tek keşfettiğinizi düşünün. 🧭
DFS ve BFS Karşılaştırması
BFS halkalar halinde yayılır; DFS ise önce derine iner. İkisi de erişilebilen her düğümü ziyaret eder, ancak bunu çok farklı bir sırayla yapar.
Özyinelemeli Yapı
Özyinelemeli DFS bir düğümü ziyaret edildi olarak işaretler, ardından ziyaret edilmemiş her komşu için kendisini çağırır. Çağrı yığını nereye dönüleceğini hatırlar.
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)Özyinelemeden Önce İşaretleyin
Komşuları keşfetmeden önce, bir düğüme girer girmez ziyaret edildi durumunu ayarlayın. Aksi hâlde döngüler DFS'yi sonsuz özyinelemeye sokar.
Özyineleme Sınırı Tuzağı
Python, özyinelemeyi yaklaşık 1000 çağrıyla sınırlar. Derin bir grafik RecursionError oluşturur ve bu da çalışma zamanı hatası sonucu olarak görünür.
Sınırı Yükseltin
Hızlı çözümlerden biri, sınırı setrecursionlimit ile yükseltmektir. DFS'yi çalıştırmadan önce sınırı en kötü durumdaki derinliğinizin üzerine ayarlayın.
import sys
sys.setrecursionlimit(300000)Bunun Yerine Döngüsel Kullanım
En güvenli çözüm, kendi yığınınızı kullanan döngüsel bir DFS'dir. Çağrı derinliği olmadığından özyineleme çökmesi de yaşanmaz.
stack = [start]Yığından Üsttekini Çıkarın
Her adımda yığının üstündeki elemanı çıkarın. Son giren ilk çıkar kuralı, DFS'nin en son eklenen yolu önce derinlemesine izlemesini sağlar.
u = stack.pop()Komşuları Yığına Ekleyin
u'yu çıkardıktan sonra ziyaret edilmemiş her komşuyu yığına ekleyin. Yeniden eklenmemeleri için onları işaretleyin.
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Tam Döngüsel Uygulama
Yığında düğüm bulunduğu sürece çıkarma ve ekleme işlemlerini tekrarlayın. Yığın boşaldığında erişilebilen her düğüm ziyaret edilmiş olur.
while stack:
u = stack.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)BFS ile Aynı Maliyet
BFS gibi DFS de her düğümü ve kenarı bir kez ziyaret eder; bu nedenle O(n + m) zamanda çalışır. Yapılacak işe hangi sıranın daha uygun olduğuna göre seçim yapın.
Hızlı Kontrol
Özyinelemeli DFS'niz derin bir grafikte çöküyor. Neden?
Özet
DFS'yi özyinelemeli olarak veya kendi yığınınızla çalıştırabilir, girişte düğümleri ziyaret edildi olarak işaretleyebilir ve grafik derinleştiğinde döngüsel yönteme geçebilirsiniz. 🎉
Sıkça Sorulan Sorular
“DFS, Özyineleme ve Yinelemeli Yığınlar” dersi ücretsiz mi?
Evet — “DFS, Özyineleme ve Yinelemeli Yığınlar” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve Competitive Programming Academy kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Competitive Programming Academy kursu toplamda 4 dersten oluşur.
“DFS, Özyineleme ve Yinelemeli Yığınlar” dersinde ne öğreneceğim?
Derinlemesine keşfedin ve özyineleme sınırlarından kaçının. Competitive Programming Academy ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
Competitive Programming Academy öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Competitive Programming Academy, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.
“DFS, Özyineleme ve Yinelemeli Yığınlar” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu Competitive Programming Academy dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Competitive Programming Academy dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Girdiden Komşuluk Listeleri
- Ağırlıksız En Kısa Yollar için BFS
- DFS, Özyineleme ve Yinelemeli Yığınlar
- Bağlantılı Bileşenler ve Taşma Doldurma