Özet - DFS

Bir graph'ta DFS uygulayıp sırayı yazdıran mini görev yaparsın.

Özet - DFS

DFS; yığın veya recursion ile derine inen, çıkmazda geri izleme yapan aramadır. Yol bulma, döngü tespiti ve topolojik sıralamada kullanılır.

Bu mini görevde DFS uygulayıp ziyaret sırasını yazdıracaksın; tüm adımları birleştir.

DFS, derin graph'ları verimli gezer; bu yüzden bağlantı analizi ve sıralama için tercih edilir.

Uygulama DFS yazdır

dfs_print(graph, start) yaz. Yığınla DFS yapıp ziyaret sırasını print() ile yazdır. Çıktı: [0, 2, 3, 1].

Örnek çözümü göster

def dfs_print(graph, start):
    # DFS sırasını yazdır
    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)
    print(visited)
dfs_print({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)

Kendini test et

Özet - DFS: kavramları eşleştir

DFS

Yığın
recursion

Kendini çağırır
backtrack

Geri dön
visited

Tekrar yok
Yığın işlemi
```
node = stack.____
```
Cevabı göster
```
node = stack.pop()
```
DFS'nin zaman karmaşıklığı nedir?
- O(V log V)
- O(V + E)
- O(E^2)
- O(V!)
Cevabı göster

O(V + E) — O(V + E).

Sıradaki ders: Greedy yaklaşım

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler