BFS ve DFS
İçerik
- İçindekiler: BFS ve DFS Arasındaki Fark
- Karşılaştırma Tablosu
- BFS
- DFS
- Anahtar Farklılıklar
- Sonuç
- Açıklayıcı Video
Genişlik birinci arama olan BFS ile derinlik ilk arama olan DFS arasındaki fark, genişlik ilk arama olan ziyaret edilen köşeleri depolamak için bir sıra kullanan grafik tarama yöntemidir, oysaki ilk arama, yığını kullanan grafik tarama yöntemidir ziyaret edilen köşeleri saklamak için.
Nefes ilk arama ve derin ilk arama, bilgisayar programcılığındaki en önemli kavramlardan biridir. Derinlik ilk arama, baştan sona bir uçtan uca olan bir yol izler, öte yandan ilk arama iş seviyesini seviyesine göre ekmek. Ana farktan bahsedersek, o zaman genişlik ilk arama olan BFS ile derinlik ilk arama olan DFS arasındaki temel fark, genişlik ilk arama, ziyaret edilen köşeleri saklamak için bir sıra kullanan grafik tarama yöntemidir, oysaki derinlik ilk arama ziyaret edilen köşeleri depolamak için yığını kullanan grafik gezme yöntemidir. BFS olarak adlandırılan genişlik ilk araması, BFS, grafikte gezinmek için kullanılır. Kuyruk, ziyaret edilen köşeleri BFS'de depolamak için kullanılır. BFS köşeleri üzerinde çalışır, ziyaret edilen köşeler sıraya kaydedilir. Vertices birer birer saklanır. Bir grafikteki her düğüm tamamen araştırılır ve grafiğin diğer köşeleri ziyaret edilir.
Derinlik İlk olarak DFS olarak bilinen arama, aynı zamanda köşeleri depolamak için yığını kullanan bir grafik geçiş yöntemidir. Genişlik birinci arama, kenar temelli yöntem değildir, oysa ilk derinlikte arama kenar temelli yöntemdir. Derinlik ilk arama, köşelerin kenarlardan keşfedildiği özyinelemeli bir şekilde çalışır. Derinlemesine ilk aramada, her köşe iki kez denetlenen bir kez ziyaret edilir.
İçindekiler: BFS ve DFS Arasındaki Fark
- Karşılaştırma Tablosu
- BFS
- DFS
- Anahtar Farklılıklar
- Sonuç
- Açıklayıcı Video
Karşılaştırma Tablosu
temel | BFS | DFS |
anlam | Genişlik ilk arama, ziyaret edilen köşeleri depolamak için bir sıra kullanan grafik tarama yöntemidir | Derinlik ilk arama, ziyaret edilen köşeleri depolamak için yığını kullanan grafik geçiş yöntemidir. |
Algoritma | Genişlik ilk arama, köşe tabanlı algoritmadır | Derinlik ilk arama kenar tabanlı algoritma |
Bellek | Genişlik ilk arama hafıza yetersiz | Derinlik ilk arama hafıza etkindir |
Uygulama | İki taraflı grafiği, bağlı bileşeni ve grafikte mevcut olan 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
BFS olarak adlandırılan genişlik ilk araması, BFS, grafikte gezinmek için kullanılır. Kuyruk, ziyaret edilen köşeleri BFS'de depolamak için kullanılır. BFS köşeleri üzerinde çalışır, ziyaret edilen köşeler sıraya kaydedilir. Vertices birer birer saklanır. Bir grafikteki her düğüm tamamen araştırılır ve grafiğin diğer köşeleri ziyaret edilir. Genişlik-birinci arama, grafiğin bağlı olup olmadığını bulmak için kullanılır. Genişlik birinci arama, iki taraflı bir grafiği tespit etmek için kullanılır. En kısa yolların bulunması BFS kullanılarak yapılır.
DFS
Derinlik İlk olarak DFS olarak bilinen arama, aynı zamanda köşeleri depolamak için yığını kullanan bir grafik geçiş yöntemidir. Genişlik birinci arama, kenar temelli bir yöntem değildir, oysa ilk derinlikte arama kenar temelli bir yöntemdir.Derinlik ilk arama, köşelerin kenarlardan keşfedildiği özyinelemeli bir şekilde çalışır. Derinlik ilk aramada, her köşe iki kez kontrol edilen bir kez ziyaret edilir.
Anahtar Farklılıklar
- Genişlik birinci arama, ziyaret edilen köşeleri depolamak için bir sıra kullanan grafik geçiş yöntemidir, oysa ilk derinlik arama, ziyaret edilen köşeleri depolamak için yığını kullanan grafik geçiş yöntemidir.
- Genişlik birinci arama, köşe tabanlı algoritma iken, Derinlik ilk arama, kenar tabanlı algoritma
- Genişlik birinci arama belleği yetersiz, oysa ilk derinliği arama belleği verimli.
- İki taraflı grafiği, bağlı bileşeni ve grafikte mevcut olan en kısa yolu incelerken, iki kenarlı bağlı grafiği, güçlü bir şekilde bağlı grafiği, asiklik grafiği ve topolojik sırayı inceler.
Sonuç
Yukarıdaki bu makalede, ilk nefesle arama ile derinlemesine ilk arama ile uygulama arasındaki net farkı görüyoruz.