Stack veya recursion
- Algoritmalar kursu
- Orta seviye
- Ders 58/80
- 4 dk
DFS'nin stack ya da recursion ile uygulandığını öğrenirsin.
Stack veya recursion
DFS, yığın (stack) ile açıkça ya da recursion ile örtülü uygulanır. Recursion, çağrı yığınını kullanır.
Her ikisi de LIFO davranışını verir; seçim stiline bağlıdır ve sonuç aynı kalır.
Recursion daha kısa okunur; yığın ise derin graph'larda taşmayı önler; pratikte tercih edilir.
Recursion tabanı
Recursive DFS'de taban durum (base case) ziyaret kümesidir: düğüm zaten ziyaret edilse çağrı hemen döner.
Sonsuz döngüyü önlemek için bu kontrol şarttır; her düğüm yalnız bir kez işlenir.
Taban durum, recursive çağrıyı durdurur ve stack overflow riskini azaltır; bu yüzden önemlidir.
Uygulama Recursive DFS
dfs_rec(graph, node, visited) adlı recursive fonksiyon yaz. Ziyaret sırasını visited listesine ekle. v=[]; dfs_rec({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0, v); print(v) ile [0, 1, 3, 2] yazdır.
Başlangıç kodu
def dfs_rec(graph, node, visited):
# Recursive DFS uygulaÖrnek çözüm
def dfs_rec(graph, node, visited):
# Recursive DFS uygula
if node not in visited:
visited.append(node)
for nb in graph[node]:
dfs_rec(graph, nb, visited)
v = []
dfs_rec({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0, v)
print(v)Beklenen çıktı
[0, 1, 3, 2]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Recursion çıktısı
def dfs(graph, node, visited):
if node in visited:
return ____def dfs(graph, node, visited):
if node in visited:
return NoneAçıklama: None doğru.
2 Stack veya recursion: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
recursion |
Kendini çağırır |
stack |
LIFO |
taban |
Dön |
visited |
Küme |
3 Recursion DFS'de çağrı yığını ne işe yarar?
- Hash tablosu olur
- Kuyruk olur
- Heap olur
- Örtük yığın olur Doğru cevap
Açıklama: Örtük yığın olur.