Derinlik Öncelikli Arama

İngilizcesi: Depth-First Search
Türkçe karşılığı: derinlemesine arama
Okunuşu: dept först sörç

Günlük kullanımda çoğunlukla İngilizcesi tercih edilir.

Güncellendi 30 Eylül 20262 dk okuma

Kısaca

Derinlik öncelikli arama, bir yolu gidebildiği kadar izleyip sonra geri dönerek sıradaki ziyaret edilmemiş dalı keşfeden bir çizge gezinme algoritmasıdır.

Derinlik öncelikli arama (DFS) nedir?

Derinlik öncelikli arama (DFS), bir çizgeyi ya da ağacı genişlemeden önce derine giderek keşfetme algoritmasıdır. Başlangıç düğümünden ziyaret edilmemiş bir komşuya, sonra o düğümün ziyaret edilmemiş komşusuna geçer ve çıkmaz sokağa ulaşana kadar devam eder. Ardından hâlâ keşfedilmemiş komşusu olan en son düğüme geri döner ve oradan devam eder.

DFS genellikle dönüş yolunu çağrı yığınının hatırladığı özyinelemeyle ya da açık bir yığın veri yapısıyla yazılır. Döngüler onu sonsuza kadar daireler çizdirmesin diye her düğümü ziyaret edilmiş olarak işaretler. Komşuluk listesiyle DFS ulaşılabilen her köşeyi ve kenarı bir kez işler; bu yüzden O(V + E) sürede çalışır. Özyinelemeli bir DFS, ziyaret edilenler kümesi ve çağrı yığını için en kötü durumda O(V) ek bellek gerektirir; ziyaret edilenler kümesine ihtiyaç duymayan bir ağaçta ise yığın yalnızca ağacın yüksekliği kadar derinleşir.

Yolunuzu tebeşirle işaretleyerek bir labirenti keşfetmek iyi bir resimdir: bir koridoru sonuna kadar izler, sonra son kavşağa geri yürür ve henüz işaretlemediğiniz bir dönüşü denersiniz. DFS; döngü tespitinin, topolojik sıralamanın (derleme araçları ve paket yöneticilerinin yaptığı gibi her görevin bağımlılıklarından sonra gelecek şekilde sıralanması), bağlantılı bileşenleri bulmanın ve labirent ile sudoku gibi bulmacaları geri izleme (backtracking) ile çözmenin temelidir. Preorder, inorder ve postorder ağaç gezinmelerinin hepsi DFS biçimleridir.

DFS en çok genişlik öncelikli aramayla (BFS) karşılaştırılır. BFS en yakın düğümleri önce keşfetmek için kuyruk kullanır ve kenar sayısına göre en kısa yolları bulur; DFS ise derine dalar ve en kısa yolu garanti etmez. Pratik bir tuzak özyineleme derinliğidir: çok derin çizgelerde özyinelemeli bir DFS dilin özyineleme sınırına takılabilir ya da stack overflow'a yol açabilir; bu yüzden açık yığınlı yinelemeli bir sürüm daha güvenlidir.

Önemli noktalar

DFS tek bir yolu olabildiğince derine izler, sonra geri döner.
Özyineleme ya da açık bir yığın, ayrıca döngüleri ele almak için bir ziyaret edilenler kümesi kullanır.
Komşuluk listesiyle O(V + E) sürede çalışır.
DFS döngü tespitinin, topolojik sıralamanın ve geri izleme bulmacalarının temelidir.
BFS'nin aksine DFS en kısa yolu garanti etmez.

Örnek

Açık bir yığınla yinelemeli derinlik öncelikli aramapython

def dfs(graph, start):
    visited, order = set(), []
    stack = [start]  # last in, first out: the newest path is explored first
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        # Push neighbors in reverse so the first neighbor is explored first
        stack.extend(reversed(graph[node]))
    return order

graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": ["A"]}  # E -> A is a cycle
print(dfs(graph, "A"))  # ['A', 'B', 'D', 'C', 'E']

Sık sorulan sorular

DFS ile BFS arasındaki fark nedir?

DFS, bir yığın ya da özyineleme kullanarak geri dönmeden önce tek bir yol boyunca olabildiğince derine gider. BFS ise bir kuyruk kullanarak daha uzağa gitmeden önce mevcut uzaklıktaki tüm düğümleri keşfeder; kenar sayısına göre en kısa yolları BFS'nin bulup DFS'nin bulmamasının nedeni budur.

DFS özyinelemeli midir?

Çoğunlukla özyinelemeli yazılır, çünkü çağrı yığını dönüş yolunu doğal olarak hatırlar. Çok derin çizgelerde özyineleme sınırlarından ve stack overflow'dan kaçınan açık bir yığınla da yazılabilir.

DFS ne için kullanılır?

Yaygın kullanımları arasında döngü tespiti, bağımlılıkların topolojik sıralaması, bağlantılı bileşenleri bulma, olası her yolu keşfetme ve labirent ile sudoku gibi bulmacalar için geri izleme algoritmaları bulunur.

Sık karşılaştırılanlar

BFS vs DFSBFS çizgeyi kuyrukla seviye seviye gezer ve ağırlıksız çizgede en kısa yolu bulur; DFS ise bir dalda olabildiğince derine iner, sonra geri döner.

İlgili sayfalar

Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin