Derinlik öncelikli arama (DFS)
Bir grafı, tek bir yolu gidebildiği kadar derine izleyerek gezer, sonra son ayrıma geri döner. Ekrandaki yığıt bu yoldur.
- süre O(V + E)
- bellek O(V)
- yığıt kullanır
Bunlar ne demek?
- Düğüm: grafın bir noktası, burada harfli bir daire olarak çizilir.
- Kenar: iki düğümü birleştiren çizgi. Burada iki yönde de üzerinden geçilebilir.
- Komşular: bir düğüme bir kenarla bağlı düğümler. Alfabetik sırayla bakılırlar.
- Kuyruk: ilk giren ilk çıkar. BFS her zaman en uzun süredir bekleyen düğümü alır.
- Yığıt: son giren ilk çıkar. DFS her zaman en son ulaştığı düğümden devam eder.
- V ve E: düğüm ve kenar sayısı. O(V + E), her düğümün ve her kenarın sabit sayıda işlendiği anlamına gelir.
- yığıtta
- şimdiki
- bitti
- arama ağacı kenarı
- atlanan kenar
Arama A düğümünden başlar. Oynat tuşuna basın veya adım adım ilerleyin.
Boşluk: oynat veya duraklat. Sol ve sağ oklar: adım adım. Home ve End: atla.
Şunu deneyin: Döngülü grafı seçin. Her kesik çizgili kenar, zaten yığıtta olan ya da bitmiş bir düğüme geri götürür: o kenar bir döngüyü kapatır.
Nasıl çalışır
DFS kendini önce henüz görmediği ilk komşu için, sonra o düğümün ilk yeni komşusu için çağırır ve bu böyle sürer. Bir düğümün yeni komşusu kalmayınca onun çağrısı biter ve DFS bir adım geri dönüp oradaki sıradaki komşuyu dener. Açık çağrılar bir yığıt oluşturur; bu yığıt her zaman başlangıçtan şimdiki düğüme giden yoldur. Bir düğümün yanındaki sayı, onun kaçıncı sırada ziyaret edildiğini gösterir.
Ne zaman iyi bir seçimdir
Nerelere ulaşılabildiğini bulmak, döngüleri bulmak, bir labirentte yol bulmak ya da birbirine bağlı görevleri sıraya koymak için DFS kullanın. En kısa yolu bulmaz.