Derinlik Öncelikli Arama (DFS)

Derinlik öncelikli arama (DFS) nedir?

Depth-first search (DFS), bir graf veya ağacı dolaşırken mümkün olduğunca derine inen bir arama algoritmasıdır. Seçtiği bir daldan ilerler, yol tıkanınca — yani ziyaret edilmemiş komşu kalmayınca — bir adım geri atar (backtracking) ve keşfedilmemiş kenarı olan en son düğümden devam eder.

BFS''in "önce en yakınlar" yaklaşımının tersine DFS "önce en derine" der. Bu basit fark, onu belirli problem tiplerinde çok doğal bir araç yapar.

Nasıl çalışır?

DFS last-in first-out (LIFO) davranışı sergiler, bu yüzden bir stack ile ifade edilir. İki klasik yolu vardır: açık bir stack tutmak ya da recursion kullanıp dilin kendi call stack''ine yaslanmak.

• Başlangıç düğümünden bir kenarı izle ve derine in.
• Ziyaret edilmemiş komşu kalmayınca en son çatallanma noktasına geri dön.
• Keşfedilecek düğüm kalmayana kadar sürdür.

Graf döngüler içerebildiği için visited kümesi burada da şarttır; algoritmanın bir düğümü iki kez işlemesini ve takılıp kalmasını önler. Ağaçlarda döngü olmadığından bu kayıt atlanabilir. Zaman karmaşıklığı komşuluk listesiyle O(V + E), bellek en kötü durumda O(V)''dir.

Neden önemli?

DFS, geri izlemeli (backtracking) problemlerin doğal iskeletidir. Bir aday yolu sonuna kadar dener, çıkmaza girince geri döner ve başka bir yol seçer. En kısa yolu garanti etmez; buna karşılık bellek açısından çoğu durumda BFS''ten daha ekonomiktir ve "tüm olası kombinasyonları sırayla dene" tipindeki problemlere birebir oturur.

Kullanım alanları

• Topolojik sıralama (yönlü asiklik graflarda)
• Döngü tespiti, bağlı ve güçlü bağlı bileşen bulma
• Labirent ve bulmaca çözümü
• Constraint satisfaction ve backtracking problemleri (örneğin sudoku, N-vezir)
• Oyun ağaçlarında derin keşif

BFS ile farkı: BFS queue ile seviye seviye yayılır ve ağırlıksız grafta en kısa yolu bulur; DFS stack (veya recursion) ile derine iner ve en kısa yol garantisi vermez.