Stack veya recursion

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.

Örnek çözümü göster

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)

Kendini test et

Recursion çıktısı

def dfs(graph, node, visited):
    if node in visited:
        return ____

Cevabı göster

def dfs(graph, node, visited):
    if node in visited:
        return None

Stack veya recursion: kavramları eşleştir

recursion

Kendini çağırır
stack

LIFO
taban

Dön
visited

Küme
Recursion DFS'de çağrı yığını ne işe yarar?
- Hash tablosu olur
- Kuyruk olur
- Heap olur
- Örtük yığın olur
Cevabı göster

Örtük yığın olur — Örtük yığın olur.

Sıradaki ders: Geri izleme

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler