BFS ve DFS, grafik aramada kullanılan geçiş yöntemleridir. Grafik geçişi, grafiğin tüm düğümlerini ziyaret etme işlemidir. Grafik, köşelere bağlanan Vertices 'V' ve Edges 'E' grubudur.
Karşılaştırma Tablosu
| Karşılaştırma için temel | BFS | DFS |
|---|---|---|
| Temel | Köşe tabanlı algoritma | Kenar tabanlı algoritma |
| Düğümleri saklamak için kullanılan veri yapısı | kuyruk | yığın |
| Bellek tüketimi | Yetersiz | Verimli |
| Yapılan ağacın yapısı | Geniş ve kısa | Dar ve uzun |
| Çapraz moda | İlk ziyaret edilmeyen en eski köşeler incelenmiştir. | Kenar boyunca dönmeler başlangıçta incelenir. |
| Optimalliği | Maliyet açısından değil en kısa mesafeyi bulmak için idealdir. | Optimal değil |
| Uygulama | İki taraflı grafiği, bağlı bileşeni ve grafikte bulunan en kısa yolu inceler. | İki uçlu bağlı grafiği, kuvvetle bağlı grafiği, asiklik grafiği ve topolojik sırayı inceler. |
BFS'un tanımı
Genişlik İlk Arama (BFS), grafiklerde kullanılan çaprazlama yöntemidir. Ziyaret edilen köşeleri saklamak için bir kuyruk kullanır. Bu yöntemde vurgu, grafiğin köşeleri üzerindedir, ilk önce bir köşe seçildikten sonra ziyaret edilir ve işaretlenir. Ziyaret edilen tepe noktasına bitişik köşeler daha sonra ziyaret edilir ve sırayla sıraya kaydedilir. Benzer şekilde, depolanan köşeler daha sonra birer birer muamele edilir ve bitişik köşeleri ziyaret edilir. Bir düğüm, grafikteki herhangi bir düğümü ziyaret etmeden önce tamamen araştırılır, başka bir deyişle ilk önce en sığ keşfedilmemiş düğümleri geçer.
Örnek
Köşeleri A, B, C, D, E, F, G olan bir grafiğe sahibiz. A'yı başlangıç noktası olarak kabul ediyoruz. Sürece dahil olan adımlar:
- Köşe A genişletilmiş ve sıraya kaydedilir.
- A'nın B, D ve G noktalarının halefleri, Vertex A'nın çıkartıldığı sırada genişler ve sıraya kaydedilir.
- Şimdi kuyruğun ön ucunda bulunan B, ardışık E ve F köşeleriyle birlikte kaldırılır.
- Vertex D kuyruğun ön ucunda kaldırılır ve bağlı F düğümü zaten ziyaret edilir.
- Vertex G kuyruktan kaldırılır ve zaten ziyaret edilen halefi E'ye sahiptir.
- Şimdi E ve F sıradan kaldırılır ve art arda verteks C sıraya alınır ve sıraya kaydedilir.
- Sonunda C de kaldırılır ve sıra boştur, bu da bizim yaptığımız anlamına gelir.
- Üretilen Çıkış - A, B, D, G, E, F, C'dir.
BFS, grafiğin bağlı bileşenlere sahip olup olmadığını bulmakta faydalı olabilir. Ayrıca iki taraflı bir grafiğin tespitinde kullanılabilir.
Grafik köşeleri iki ayrık kümeye bölündüğünde bir grafik iki taraflıdır; aynı sette iki bitişik köşe bulunmayacaktır. İki taraflı bir grafiği kontrol etmenin bir başka yöntemi, grafikte bir tek döngü oluşumunu kontrol etmektir. İki taraflı bir grafik tek döngü içermemelidir.
BFS ayrıca grafikte ağ olarak görülebilecek en kısa yolu bulmakta daha iyidir.
DFS'un tanımı
Derinlik İlk Arama (DFS) gezinme yöntemi, ziyaret edilen köşeleri depolamak için yığını kullanır. DFS, kenar tabanlı bir yöntemdir ve köşelerin bir yol (kenar) boyunca keşfedildiği özyinelemeli şekilde çalışır. Bir düğümün keşfedilmesi, başka bir keşfedilmemiş düğüm bulunduğunda ve en derin keşfedilmemiş düğümler her şeyden önce geçildiği anda askıya alınır. DFS, her köşeyi tam olarak bir kez gezer / ziyaret eder ve her kenar tam olarak iki kez denetlenir.
Örnek
BFS'ye benzer şekilde, DFS işlemlerini gerçekleştirmek için aynı grafiği kullanmanıza izin verir ve ilgili adımlar şunlardır:
- A'yı, keşfedilen ve istifte depolanan başlangıç tepe noktası olarak kabul edin.
- B'nin ardışık B köşesi yığında saklanır.
- Vertex B iki ardışık E ve F'ye sahiptir, aralarında E alfabetik olarak önce araştırılır ve istifte depolanır.
- Köşe E'nin halefi, yani G istifte depolanır.
- Vertex G iki bağlantılı köşeye sahiptir ve her ikisi de zaten ziyaret edilmiştir, bu nedenle G yığından çıkarılır.
- Benzer şekilde, E ler de uzaklaştırılmıştır.
- Şimdi, köşe B yığının tepesinde, başka bir düğüm (köşe) F keşfedilmiş ve yığında depolanmıştır.
- Vertex F iki ardışık C ve D'ye sahiptir, aralarında C ilk önce travers edilir ve istifte depolanır.
- Vertex C yalnızca önceden ziyaret edilmiş bir öncekine sahip, bu yüzden yığından kaldırıldı.
- Şimdi F'ye bağlı köşe D ziyaret edildi ve yığında saklandı.
- Köşe D'nin hiç görülmeyen düğümleri olmadığından, D kaldırılır.
- Benzer şekilde, F, B ve A da açılır.
- Üretilen çıktı - A, B, E, G, F, C, D
DFS uygulamaları, iki kenar bağlantılı grafiğin, kuvvetle bağlanmış grafiğin, asiklik grafiğin ve topolojik düzenin incelenmesini içerir .
Bir grafiği, kenarlarından biri çıkarılsa bile, yalnızca bağlı kalması durumunda bağlanmış iki kenar olarak adlandırır. Bu uygulama, ağdaki bir bağlantının arızasının kalan ağı etkilemeyeceği ve hala bağlanabileceği bilgisayar ağlarında çok kullanışlıdır.
Güçlü bir şekilde bağlanmış grafik, sıralı köşe çiftleri arasında bir yol bulunması gereken bir grafiktir. Yönlendirilen grafikte DFS, sipariş edilen her köşe çifti arasındaki yolu aramak için kullanılır. DFS, bağlantı sorunlarını kolayca çözebilir.
BFS ve DFS Arasındaki Temel Farklar
- BFS, köşe tabanlı bir algoritma iken DFS, kenar tabanlı bir algoritmadır.
- BFS'de kuyruk veri yapısı kullanılmıştır. Öte yandan, DFS yığın veya özyineleme kullanır.
- Bellek alanı DFS'de verimli bir şekilde kullanılırken, BFS'de alan kullanımı etkili değildir.
- BFS en uygun algoritma iken, DFS en uygun değildir.
- DFS, dar ve uzun ağaçlar oluşturur. BFS, geniş ve kısa bir ağaç oluşturur.
Sonuç
Her iki grafik arama tekniğinin de BFS ve DFS'leri benzer çalışma süresine sahiptir ancak farklı alan tüketimine sahiptir, DFS doğrusal alanı alır çünkü keşfedilmemiş düğümlerle tek yolu hatırlamamız gerekirken, BFS her düğümü bellekte tutar.
DFS daha derin çözümler sunar ve en uygun değildir, ancak çözüm yoğun olduğunda iyi çalışır, oysa BFS ilk sırada en uygun hedefi arar.
