BFS ve DFS Arasındaki Fark
Genişlik İlk Arama (BFS olarak da bilinir), tüm ağların genişletilmesi için kullanılan bir arama yöntemidir. özel grafik. Bu görevi, bu düğümleri (veya bir dizi dizinin birleşimini) incelemek ve genişletmek için her bir çözümü arayarak gerçekleştirir. Bu nedenle, bir BFS sezgisel bir algoritma (veya birden çok senaryo ile bir çözüm arayan bir algoritma) kullanmaz. Tüm düğümler elde edildikten sonra, İlk Giren, Birinci Çıkışı sırası olarak bilinen bir sıraya eklenirler. Araştırılmayan bu düğümler 'açık' olarak işaretlenmiş bir kapta 'depolanır'; Bir kere araştırdıklarında 'kapalı' olarak işaretlenmiş konteynere taşınırlar.
Derinlik İlk Arama (DFS olarak da bilinir), bir hedefe ulaşılıncaya kadar (veya başka bir permütasyon ya da başka permütasyonlar olmaksızın bir düğümün bulunmasına kadar) bir aramanın bir alt düğümüne daha derin giren bir arama yöntemidir. çocukların). Bir gol bulduktan sonra, arama, tüm düğümler başarıyla aranana kadar işlemi tekrarlayan önceki bir düğüme bir geri dönüş yoluna gider. Bu nedenle, düğümler daha ileri araştırmalar için bir kenara bırakılmaya devam edilir - buna özyinelemeli olmayan uygulama denir.
BFS'nin özellikleri uzay ve zaman karmaşıklığı, eksiksizlik, tamlığın kanıtı ve optimumluğudur. Uzay karmaşıklığı, bir aramanın en derin seviyesindeki düğüm sayısının oranını ifade eder. Zaman karmaşıklığı, bir düğümün bir aramada alacağı her yolu değerlendirmek için kullanılan gerçek zaman miktarını ifade eder. Tamamlama aslında, ne tür bir grafiğe bakılmaksızın bir grafikte bir çözüm bulan bir arama yöntemidir. Tamlığın kanıtı, bir hedefteki bir düğümde belirli bir derinlikte bulunan en sığ seviyedir. Son olarak, optimumluk, ağırlıklandırılmamış bir BFS'yi ifade eder - bu, birim adım maliyeti için kullanılan bir grafiktir.
Bir DFS, tüm köşelerden oluşan ve yönlendirilmemiş bir grafikte bazı kenarlardan oluşan bir ağaç içeren bir kapsayıcı ağaç kullanarak en doğal çıktıdır. Bu oluşumda, grafik üç sınıfa ayrılmıştır: İleri kenarlar, bir düğümden bir alt düğüme işaret; arka kenarlar, bir düğümden önceki bir düğüme işaret; ve bunlardan birini yapmayan kenarlar arası.
Özet:
1. BFS, düğümlerini genişletmek için bir grafiğin her bir çözümünü arar; bir DFS, bir hedefe ulaşılana kadar bir alt düğümün derinlerine girer.
2. Bir BFS'nin özellikleri, uzay ve zaman karmaşıklığı, eksiksizlik, tamlığın kanıtı ve optimumluğudur; bir DFS için en doğal çıktı, üç sınıflı uzayan bir ağaçtır: ileri kenarlar, arka kenarlar ve çapraz kenarlar.
