DFS mantığı

Bir dalı sonuna kadar takip eden derin öncelikli aramayı öğrenirsin.

DFS mantığı

Derin öncelikli arama (DFS), bir dalı sonuna kadar takip eder, çıkmaza girince geri döner.

Bu yüzden DFS, recursion ya da yığın (stack) ile doğal olarak uygulanır; derine inme önceliklidir.

DFS, döngü tespiti, topolojik sıralama ve yol bulmada sıkça kullanılır; karmaşıklığı O(V + E) olur.

Geri izleme

Çıkmaz sokakta geri dönüp başka bir dala geçmeye backtracking denir. DFS'in temel davranışı budur.

Geri dönen dalların durumu korunur; böylece yol tamamlanır ve hiçbir dal atlanmaz.

Backtracking sayesinde DFS, döngüsel graph'larda bile her düğümü güvenle ziyaret eder.

Uygulama DFS sırası

dfs_order(graph, start) yaz. Yığınla DFS yapıp ziyaret sırasını döndür. print(dfs_order({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)) ile [0, 2, 3, 1] yazdır.

Örnek çözümü göster

def dfs_order(graph, start):
    # Yığınla DFS yap
    visited = []
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            for nb in reversed(graph[node]):
                if nb not in visited:
                    stack.append(nb)
    return visited
print(dfs_order({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0))

Kendini test et

DFS hangi veri yapısıyla doğal uygulanır?
- Yığın veya recursion
- Sadece kuyruk
- Sadece heap
- Hash tablosu
Cevabı göster

Yığın veya recursion — Yığın veya recursion.
DFS başlangıcı
```
stack = [____]
```
Cevabı göster
```
stack = [start]
```
DFS mantığı: kavramları eşleştir

DFS

Derin
stack

LIFO
BFS

Katman
recursion

Kendini çağırır

Sıradaki ders: Stack veya recursion

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler