DFS — Derinlik Öncelikli Arama Algoritması

Derinlik öncelikli arama, yani DFS, bir ağaç ya da grafiği geri izleme yapmadan önce bir yolu mümkün olduğunca derine kadar takip ederek keşfeden bir algoritmadır. Basitçe söylemek gerekirse: DFS, tıkanana kadar derine iner, sonra başka bir dalın bulunduğu son noktaya geri döner.

Tek bir fikri hatırlayacaksanız, şunu hatırlayın: DFS, "derine git, sonra geri izleme yap" demektir.

Derinlik Öncelikli Arama Ne Yapar

DFS hem ağaçlarda hem de genel graflarda kullanılabilir. Bir düğümden başlayarak tekrar tekrar ziyaret edilmemiş bir komşuya gider. Ziyaret edilmemiş komşusu kalmayan bir düğüme ulaştığında, önceki düğüme geri izler ve oradan devam eder.

Bu geri izleme, DFS'nin ayırt edici davranışıdır. Özyinelemeli uygulamalarda bunu çağrı yığını otomatik olarak yapar. Yinelemeli uygulamalarda ise aynı rolü açık bir yığın üstlenir.

DFS Sırası Neden Değişebilir

DFS tek bir evrensel ziyaret sırası üretmez. Tam sıra, komşuların hangi sırayla ele alındığına bağlıdır.

Örneğin, bir düğümün komşuları $B$ ve $C$ ise, önce $B$'yi ziyaret etmek, önce $C$'yi ziyaret etmekten farklı bir DFS sırası verebilir. Her iki durumda da arama DFS'dir çünkü kural aynıdır: kardeş bir dalı keşfetmeden önce derine gitmeye devam et.

Küçük Bir Grafikte DFS Örneği

Grafiğin şu bağlantılara sahip olduğunu varsayalım:

• $A$, $B$ ve $C$'ye bağlı
• $B$, $D$ ve $E$'ye bağlı
• $C$, $F$'ye bağlı

Komşuları her zaman soldan sağa incelediğimizi ve $A$'dan başladığımızı varsayalım.

DFS şu şekilde ilerler:

1. $A$'yı ziyaret et
2. $B$'ye git
3. $D$'ye git
4. $D$'nin ziyaret edilmemiş komşusu yok, bu yüzden $B$'ye geri izle
5. $B$'den $E$'ye git
6. $E$ tamamlandı, bu yüzden $B$'ye, sonra $A$'ya geri izle
7. $A$'dan $C$'ye git
8. $C$'den $F$'ye git

Dolayısıyla geçerli bir DFS ziyaret sırası şudur:

$$A, B, D, E, C, F$$

Temel fikir şudur: DFS, $A \to B$ tarafını bitirmeden $A \to C$ tarafına başlamaz. Komşu sırasını değiştirirseniz, ziyaret sırası da değişebilir.

Geri İzleme Neden Yığın Kullanır

DFS, çıkmaza ulaştıktan sonra nereye döneceğini hatırlamak için her zaman bir yola ihtiyaç duyar. Bu yüzden yığınlar DFS'de doğal olarak ortaya çıkar.

Özyinelemeli DFS'de, her fonksiyon çağrısı arama derine giderken bekler ve program geri izleme sırasında ters sırada döner. Yinelemeli DFS'de ise düğümleri bir yığına eklersiniz ve en son tamamlanmamış noktadan devam etme zamanı geldiğinde onları yığından çıkarırsınız.

DFS Zaman ve Alan Karmaşıklığı

Grafik bir komşuluk listesi olarak tutuluyorsa ve her tepe ilk ziyaret edildiğinde işaretleniyorsa, DFS grafiğin erişilebilir kısmı için

$$O(V + E)$$

zamanda çalışır; burada $V$ tepe sayısı, $E$ ise kenar sayısıdır.

Ek alan genellikle

$$O(V)$$

olur; çünkü ziyaret edilenler yapısı ile özyineleme yığını veya açık yığın, tepe sayısıyla birlikte büyüyebilir.

Yaygın DFS Hataları

Ziyaret Edilen Düğümleri İşaretlemeyi Unutmak

Genel bir grafikte, ziyaret kontrolünü unutmak DFS'nin bir döngü içinde sonsuza kadar dönmesine neden olabilir. Bir ağaç yönsüz bir grafik olarak tutulsa bile, kodunuz bu durumu açıkça ele almıyorsa ebeveyne hemen geri yürümekten kaçınmanız gerekir.

DFS'nin En Kısa Yolu Bulduğunu Varsaymak

DFS bir yol bulabilir, ancak ağırlıksız bir grafikte genel olarak en kısa yolu garanti etmez. Amaç en kısa yolsa ve tüm kenarlar eşit ağırlıktaysa, genellikle doğru başlangıç noktası BFS'dir.

DFS Sırasını Tek ve Değişmez Sanmak

Sıra, komşu sırasına bağlıdır. Bu sıra değişirse, dolaşma sırası da değişebilir.

Derinlik Öncelikli Arama Ne Zaman Kullanılır

DFS, en yakın mesafeyi önce bulmaktan ziyade yapıyı keşfetmek istediğinizde kullanışlıdır. Yaygın kullanım alanları şunlardır:

• bir düğüme erişilip erişilemeyeceğini kontrol etmek
• bağlı bileşenleri bulmak
• bazı grafik ayarlarında döngü tespiti yapmak
• ağaçları dolaşmak
• labirentler veya bulmaca araması gibi geri izleme tarzı problemleri çözmek

Bu kadar sık karşımıza çıkmasının temel nedeni, "derine git, sonra geri izleme yap" fikrinin birçok özyinelemeli problem yapısıyla uyuşmasıdır.

DFS ve BFS: Pratik Fark

DFS önce bir dal boyunca aşağı iner. BFS ise bir sonraki uzaklığa geçmeden önce aynı uzaklıktaki tüm düğümleri keşfeder.

Kapsamlı keşif ya da özyinelemeli yapı sizin için önemliyse, DFS çoğu zaman doğaldır. Ağırlıksız bir grafikte en kısa yol önemliyse, BFS genellikle daha güvenli ilk tercihtir.

Benzer Bir Dolaşmayı Deneyin

Altı düğümlü küçük bir grafik çizin ve sabit bir komşu sırası seçin. DFS'yi elle çalıştırın ve tam olarak ne zaman ileri gittiğinizi, ne zaman geri izlediğinizi yazın. Komşuları yeniden sıraladıktan sonra sıranız değişiyorsa, bu bir hata değildir. Bu, DFS'nin çalışma biçiminin bir parçasıdır.