Derinlik öncelikli arama (DFS)
Bir labirente girin, çıkmaza girene kadar ilerleyin, sonra son yol ayrımına dönün ve sıradaki yolu deneyin. Derinlik öncelikli arama bir grafı aynı şekilde keşfeder. En basit graf algoritmalarından biridir ve tuttuğu yığın size beklediğinizden fazlasını anlatır.
Fikir
Graf, kenarlarla birbirine bağlanan düğümlerden oluşan bir kümedir: odalar ve kapılar, web sayfaları ve bağlantılar, görevler ve bağlı oldukları görevler. Derinlik öncelikli arama, bir başlangıçtan ulaşabildiği her düğümü ziyaret eder, ama belirli bir sırayla: her zaman en son ulaştığı düğümden devam eder. İçinde bulunduğu düğümlerin bir yığınını tutar. Yeni bir düğüm tepeye eklenir; bir düğüm ancak çevresindeki her şey keşfedildiğinde yığından çıkar.
Adım adım
Başlangıcı yığına koyun ve ona 1 ziyaret numarasını verin. Tepedeki düğümün sıradaki komşusuna bakın. Görülmemişse ona sıradaki ziyaret numarasını verin, ona hangi düğümden ulaşıldığını hatırlayın ve onu yığının tepesine koyun. Daha önce görülmüşse atlayın. Tepedeki düğümün bakılacak komşusu kalmadığında düğüm tamamlanmıştır: onu çıkarın ve altındaki düğümle devam edin. Yığın boşaldığında ya da hedefe ulaşıldığında durun.
Bir örnek
A–B, A–C, B–D, C–D, C–E ve D–F kenarlarından oluşan bir graf alın, A'dan başlayın ve komşulara alfabetik sırayla bakın. Arama A'dan B'ye, B'den D'ye, D'den C'ye ve C'den E'ye gider; yani yığın A, B, D, C, E olur. Yolda C, hâlâ yığında olan A'yı görür: C–A kenarı A, B, D, C döngüsünü kapatır. E'de yeni bir şey yoktur, bu yüzden tamamlanır, ardından C tamamlanır ve arama hâlâ F'ye sahip olan D'ye geri döner. Ziyaret sırası A, B, D, C, E, F'dir. Hedef E ise DFS, A → B → D → C → E yoluyla, yani dört kenarla durur; oysa A → C → E yalnızca iki kenardır.
Ne işe yarar
Yığın her zaman başlangıçtan mevcut düğüme giden bir yoldur; bu da DFS'yi labirentler ve bulmacalar için doğal kılar: geri izlemenin (backtracking) ardındaki fikir budur. Yönsüz bir grafta, hâlâ yığında olan bir düğüme giden kenar bir döngüyü kapatır. Yönlü bir grafta düğümleri tamamlanma sırasının tersiyle listelemek topolojik bir sıra verir; böylece görevler, bağlı oldukları görevlerden sonra gelir. Derinlik öncelikli arama bağlantılı bileşenleri, köprüleri ve eklem noktalarını da bulur; rastgele sürümü ise labirent üretmenin klasik bir yoludur.
Tarihçe
19. yüzyılda Fransız matematikçi Charles Pierre Trémaux, geçitleri işaretleyerek herhangi bir labirentten çıkmanın bir yolunu tarif etti; bu, tebeşirle yapılan derinlik öncelikli aramadır. 1972 ve 1973'te Robert Tarjan ve John Hopcroft, DFS'nin güçlü bağlantılı bileşenlerden bir grafın kesişme olmadan çizilip çizilemeyeceğini sınamaya kadar pek çok graf problemini doğrusal zamanda çözdüğünü gösterdi. 1986 Turing Ödülü'nü kısmen bu çalışma için aldılar.
Keşfedin
Uygulamayı açın ve Adım'a basın. Komşularına bakılan düğüm vurgulanır, yığındaki düğümler mavi, tamamlanan düğümler yeşildir ve her birinde ziyaret numarası yazar. Yığın, grafın altında başlangıçtan tepedeki düğüme kadar gösterilir. Döngü kapatan kenarlar için durum satırını izleyin ve genişlik öncelikli aramaya kıyasla bulunan yolun ne kadar uzun olabileceğini görmek için bir hedef seçin.
Sık sorulan sorular
DFS'nin zaman karmaşıklığı nedir?
V düğüm (köşe) ve E kenar için O(V + E): her düğüm yığına bir kez girer ve bir kez çıkar, her kenar da iki ucundan incelenir. Yığın ve işaretler için O(V) ek bellek gerekir.
DFS neden yığın kullanır?
Çünkü son giren ilk çıkar ilkesi, aramanın en yeni düğümden devam etmesini ve bir öncekine geri dönmesini sağlar. Özyineleme de aynı şeyi programın çağrı yığınıyla yapar. Yığın yerine kuyruk kullanılsaydı arama halka halka yayılırdı: bu da genişlik öncelikli aramadır.
Özyinelemeli DFS büyük graflarda sorun olur mu?
Olabilir: uzun bir yol derin özyineleme demektir ve birçok dil çağrıların ne kadar derine inebileceğini sınırlar. Açık bir yığınla yinelemeli çalışmak bu sınırdan kaçınır ve düğümleri aynı sırayla ziyaret eder.
DFS nerede kullanılır?
Labirentleri ve bulmacaları geri izlemeyle çözmede, döngüleri bulmada, görevleri bağımlılıklarına göre sıralamada (topolojik sıralama), bağlantılı ve güçlü bağlantılı bileşenleri bulmada, labirent üretmede ve bağımlılık graflarını dolaşan derleyicilerde ve derleme araçlarında.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Derinlik öncelikli aramayı deneyin