Geri izleme
- Algoritmalar kursu
- Orta seviye
- Ders 59/80
- 4 dk
Çıkmaz sokakta geri dönüp yeni dal denemeyi öğrenirsin.
Geri izleme uygulaması
DFS, çıkmaz bir dala girince bir adım geri döner ve bir önceki düzeyden yeni bir dal dener.
Yığın tabanlı DFS'te geri dönüş, yığından pop yapmakla doğal olarak gerçekleşir; ek kod gerekmez.
Bu sayede DFS, derin graph'larda bile tüm dalları sistemle gezer; hiçbir dal atlanmaz.
Yol tamamlama
Geri izleme sırasında ziyaret kümesi sayesinde her düğüm yalnızca bir kez işlenir; bu da verimli yol keşfini sağlar.
Bu, DFS'i döngüsel graph'ta bile güvenli yapar; sonsuz döngü oluşmaz.
Ziyaret kümesi, geri dönüş sırasında tekrarı önler ve doğru yol tamamlanmasını sağlar.
Uygulama DFS derinliği
dfs_depth(graph, start) yaz. Yığınla DFS yapıp ulaşılan en büyük derinliği döndür. print(dfs_depth({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)) ile 3 yazdır.
Başlangıç kodu
def dfs_depth(graph, start):
# En büyük derinliği bulÖrnek çözüm
def dfs_depth(graph, start):
# En büyük derinliği bul
visited = set()
stack = [(start, 0)]
max_depth = 0
while stack:
node, depth = stack.pop()
if node not in visited:
visited.add(node)
if depth > max_depth:
max_depth = depth
for nb in graph[node]:
if nb not in visited:
stack.append((nb, depth + 1))
return max_depth
print(dfs_depth({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0))Beklenen çıktı
3
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Geri izleme: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
backtrack |
Geri dön |
dead end |
Çıkmaz |
pop |
Geri al |
visited |
Tekrar yok |
2 Yığın tabanlı DFS'te geri izleme nasıl gerçekleşir?
- Yığından pop ile Doğru cevap
- Kuyruktan pop ile
- Heap'ten çekerek
- Hash ile
Açıklama: Yığından pop ile.
3 Geri alma
node = stack.____node = stack.pop()Açıklama: pop() doğru.