Geri izleme

Çı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.

Örnek çözümü göster

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))

Kendini test et

Geri izleme: kavramları eşleştir

backtrack

Geri dön
dead end

Çıkmaz
pop

Geri al
visited

Tekrar yok
Yığın tabanlı DFS'te geri izleme nasıl gerçekleşir?
- Yığından pop ile
- Kuyruktan pop ile
- Heap'ten çekerek
- Hash ile
Cevabı göster

Yığından pop ile — Yığından pop ile.
Geri alma
```
node = stack.____
```
Cevabı göster
```
node = stack.pop()
```

Sıradaki ders: Özet - DFS

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler