Derinlik Öncelikli Arama (DFS)

#Nasıl çalışır?

Derinlik öncelikli arama (Depth-First Search, DFS), bir graftaki bir dalı gidebildiği kadar derine izler; çıkmaza girince en son ayrıldığı noktaya geri döner (backtracking) ve oradan başka bir dalı dener.

Bu davranışı bir yığın (stack) sağlar: genellikle özyineleme ile yazılır, bu durumda yığın çağrı yığınının kendisidir. Herhangi bir anda yığındaki düğümler, başlangıçtan şu anki düğüme giden yolu oluşturur.

DFS iki düğüm arasında bir yol bulur ama bu yolun en kısa olacağını garanti etmez. Buna karşılık döngü bulma, topolojik sıralama ve bağlı bileşenler gibi yapısal sorular için çok uygundur.

#Kendin dene

#Adım adım

1. 01Başlangıç düğümünü ziyaret et ve yığına koy.
2. 02Ziyaret edilmemiş ilk komşuya geç ve aynı işlemi orada tekrarla.
3. 03Ziyaret edilmemiş komşu kalmadıysa düğümü yığından çıkar ve bir öncekine geri dön (backtrack).
4. 04Yol bulmak için: hedefe ulaşıldığında yığın, başlangıçtan hedefe giden yoldur.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

# Undirected graph as adjacency lists (neighbours in increasing order).
EDGES = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 7), (5, 7), (6, 7)]
graph = {v: [] for v in range(1, 8)}
for a, b in EDGES:
    graph[a].append(b)
    graph[b].append(a)
for v in graph:
    graph[v].sort()


def dfs(u: int, visited: set, order: list) -> list:
    visited.add(u)
    order.append(u)
    for v in graph[u]:
        if v not in visited:
            dfs(v, visited, order)  # go deep first; returning = backtracking
    return order


def find_path(u: int, target: int, visited: set, path: list) -> bool:
    visited.add(u)
    path.append(u)
    if u == target:
        return True
    for v in graph[u]:
        if v not in visited and find_path(v, target, visited, path):
            return True
    path.pop()  # dead end
    return False


print(" ".join(map(str, dfs(1, set(), []))))
path = []
find_path(1, 6, set(), path)
print(" ".join(map(str, path)))  # a path, but not the shortest (1 3 6)

#Karmaşıklık

Her düğüm bir kez ziyaret edilir ve her kenara iki uçtan birer kez bakılır. Özyinelemeli DFS çok derin graflarda (ör. 1 milyon düğümlük bir zincir) çağrı yığınını taşırabilir; o durumda açık bir yığınla iteratif yazmak gerekir.

#Ne zaman kullanılır?

Labirent üretme ve çözme, bulmaca/backtracking problemleri (Sudoku, N-vezir), döngü tespiti, topolojik sıralama (derleme ve görev bağımlılıkları), bağlı ve güçlü bağlı bileşenler, köprü ve kesme noktaları DFS ile çözülür.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.