- Şu anki
- Yığında
- Tamamlanan
- Yol
Derinlik öncelikli arama (DFS)
Derinlik öncelikli arama, bir grafı bir eli duvarda labirentte yürüyen biri gibi keşfeder: bir yolu gidebildiği kadar izler ve ancak gidecek yeni bir yer kalmadığında geri döner. Bunu bir yığınla yapar. Başlamak için bir düğüme tıklayın, isterseniz bir hedef seçin ve aramayı adım adım ilerletin: yığının büyüyüp küçüldüğünü, her düğümün ziyaret numarasını aldığını ve döngü kapatan kenarları görün. Aramayı izlemek için Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Bir düğümü başlangıç yapmak için ona tıklayın; tıklamayı Hedef'e çevirip başka bir düğüme tıklayarak oraya giden bir yol arayın. Her düğümdeki sayı, o düğümün ziyaret edilme sırasıdır; grafın altındaki satır ise başlangıçtan tepedeki düğüme kadar yığındır. Yeni graf başka bir graf oluşturur; kaç düğüm ve kenar olacağını seçin. Pano seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.
Nasıl çalışır
- Bir düğümü başlangıç yapmak için ona tıklayın. Yol aramak için tıklamayı Hedef'e çevirin ve başka bir düğüme tıklayın.
- Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Aramada herhangi bir yere atlamak için adım kaydırıcısını sürükleyin.
- Grafın altındaki yığını ve her düğümdeki ziyaret numarasını izleyin. Yeni graf, denemeniz için başka bir graf oluşturur.
Derinlik öncelikli arama nasıl çalışır
Başlangıç düğümünü yığına koyun. Sonra şunu tekrarlayın: yığının tepesindeki düğümün sıradaki komşusuna bakın. Henüz görülmemiş bir komşu sıradaki ziyaret numarasını alır, kendisine hangi düğümden ulaşıldığını hatırlar ve yığının tepesine eklenir; böylece arama oradan devam eder. Tepedeki düğümün bakılacak komşusu kalmadığında düğüm tamamlanır ve yığından çıkar, arama da altındaki düğüme geri döner. Yığın boşaldığında ulaşılabilen her düğüm ziyaret edilmiştir.
Yığın size ne söyler
Arama her zaman en yeni düğümden devam ettiği için yığın her zaman başlangıçtan incelenen düğüme giden bir yoldur. Hedefe ulaşıldığında yığın ona giden bir yoldur, ama genellikle en kısası değildir: onu genişlik öncelikli arama bulur. Yönsüz bir grafta, hâlâ yığında olan ve az önce gelinen düğüm olmayan bir düğüme giden kenar bir döngüyü kapatır. Hatırlanan düğümler bir ağaç oluşturur, derinlik öncelikli ağaç; düğümlerin tamamlanma sırası ise topolojik sıralamanın anahtarıdır.
Sık sorulan sorular
Derinlik öncelikli arama nedir?
Bir grafı bir başlangıç düğümünden keşfetmenin bir yolu: bir yolu gidebildiği kadar derine izler ve ancak gidecek yeni bir yer kalmadığında başka bir dalı denemek için geri döner. Geri dönüş yolunu hatırlamak için bir yığın ya da özyineleme kullanır.
Derinlik öncelikli arama en kısa yolu bulur mu?
Hayır. Varsa hedefe giden bir yol bulur, ama bu yol gerekenden çok daha uzun olabilir, çünkü DFS denediği ilk dala bağlı kalır. En az kenar için genişlik öncelikli aramayı, kenarların uzunlukları varsa Dijkstra algoritmasını kullanın.
DFS ile BFS arasındaki fark nedir?
Derinlik öncelikli arama bir yığın kullanır ve geri dönmeden önce tek bir yol boyunca derine iner. Genişlik öncelikli arama bir kuyruk kullanır ve halka halka eşit biçimde yayılır. İkisi de ulaşılabilen her düğümü, düğüm sayısı artı kenar sayısıyla büyüyen bir sürede ziyaret eder; BFS en kısa yolları bulur, DFS ise döngüler, labirentler ve topolojik sıralama için doğal seçimdir.
DFS bir döngüyü nasıl bulur?
Yönsüz bir grafta arama, hâlâ yığında olan bir düğüme giden bir kenarla karşılaşırsa ve o düğüm az önce geldiği düğüm değilse, bu kenar bir döngüyü kapatır. Uygulamada bu olduğunda durum satırı bunu söyler.
Grafım bir yere gönderiliyor mu?
Hayır. Graf tarayıcınızda oluşturulur ve aranır, son ayarlarınız da bu tarayıcının yerel depolamasında kalır.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Editöre Git