Genişlik Öncelikli Arama
- İngilizcesi
- Breadth-First Search
- Türkçe karşılığı
- enine arama
- Okunuşu
- bredt först sörç
Günlük kullanımda çoğunlukla İngilizcesi tercih edilir.
Kısaca
Genişlik öncelikli arama, düğümleri başlangıca uzaklık sırasıyla ziyaret eden ve derine inmeden önce tüm komşuları keşfeden bir çizge gezinme algoritmasıdır.
Genişlik öncelikli arama (BFS) nedir?
Genişlik öncelikli arama (BFS), bir çizgeyi ya da ağacı seviye seviye keşfetme algoritmasıdır. Bir düğümden başlar, o düğümün tüm doğrudan komşularını, sonra onların tüm komşularını ziyaret eder ve böyle halkalar halinde dışa doğru ilerler. Sonuç olarak her düğüme, başlangıçtan kaç kenar uzakta olduğu sırasıyla ulaşır.
BFS, keşfedilmeyi bekleyen düğümlerin bir kuyruğunu tutar; dışa doğru eşit biçimde genişlemesini sağlayan budur. Kuyruğun önündeki düğümü çıkarır, daha önce görmediği her komşuyu arkaya ekler ve döngülerin sonsuza kadar dönmesine yol açmasın diye bu komşuları ziyaret edilmiş olarak işaretler. Komşuluk listesiyle BFS ulaşılabilen her köşeyi ve kenarı bir kez işler; bu yüzden O(V + E) sürede çalışır (V köşe sayısı, E kenar sayısı) ve kuyruk ile ziyaret edilenler kümesi için O(V) ek bellek gerektirir.
Bir göle atılan taştan yayılan dalgaları düşünün: merkeze en yakın halka önce oluşur, sonra bir sonrakisi ve böyle devam eder. Bu nedenle BFS, ağırlıksız bir çizgede kenar sayısına göre en kısa yolu bulur; örneğin bir bulmacayı çözmek için gereken en az hamle, iki ağ cihazı arasındaki en az atlama ya da bir sosyal ağdaki iki kişi arasındaki ayrılık derecesi gibi. Web tarayıcıları ve ağaçların seviye sıralı gezinmesi de BFS kullanır.
BFS en sık derinlik öncelikli aramayla (DFS) karşılaştırılır. DFS geri dönmeden önce tek bir yolu olabildiğince derine izlemek için yığın ya da özyineleme kullanırken BFS en yakın düğümleri önce keşfetmek için kuyruk kullanır; ikisi de O(V + E) sürer. BFS en kısa yolları yalnızca her kenar aynı maliyetteyse garanti eder; bu yüzden ağırlıklı çizgeler bunun yerine Dijkstra algoritmasına ihtiyaç duyar. Çok geniş çizgelerde ise BFS çok bellek kullanabilir, çünkü bir seviyenin tamamı aynı anda kuyrukta bekleyebilir.
Önemli noktalar
- BFS bir çizgeyi seviye seviye keşfeder, en yakın düğümleri önce ziyaret eder.
- Bir kuyruk ve hiçbir düğümün iki kez işlenmemesi için bir ziyaret edilenler kümesi kullanır.
- Komşuluk listesiyle O(V + E) sürede çalışır ve O(V) ek bellek kullanır.
- BFS, ağırlıksız bir çizgede kenar sayısına göre en kısa yolu bulur.
- BFS kuyrukla genişlemesine, DFS yığınla derinlemesine gider.
Örnek
from collections import deque
def bfs_distances(graph, start):
distance = {start: 0} # also serves as the visited set
queue = deque([start])
while queue:
node = queue.popleft() # O(1): take the oldest, closest node first
for neighbor in graph[node]:
if neighbor not in distance: # skip nodes already seen
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
return distance
friends = {"ana": ["ben", "cy"], "ben": ["dee"], "cy": ["dee"], "dee": ["eve"], "eve": []}
print(bfs_distances(friends, "ana")) # {'ana': 0, 'ben': 1, 'cy': 1, 'dee': 2, 'eve': 3}Sık sorulan sorular
BFS ile DFS arasındaki fark nedir?
BFS, bir kuyruk kullanarak daha uzağa geçmeden önce mevcut uzaklıktaki tüm düğümleri keşfeder. DFS ise bir yığın ya da özyineleme kullanarak geri dönmeden önce tek bir yolu olabildiğince derine izler. İkisi de O(V + E) sürede çalışır, ancak kenar sayısına göre en kısa yolları yalnızca BFS bulur.
BFS her zaman en kısa yolu bulur mu?
En az kenarlı yolu bulur; bu da tüm kenarlar aynı maliyetteyse en kısa yoldur. Kenarların yol mesafeleri gibi farklı ağırlıkları olduğunda bunun yerine Dijkstra algoritmasını kullanın.
Genişlik öncelikli aramanın zaman karmaşıklığı nedir?
Komşuluk listesiyle BFS, her köşeyi ve her kenarı sabit sayıda işlediği için O(V + E) sürede çalışır. Komşuluk matrisiyle ise her düğümün komşularını bulmak bir satırın tamamını taramak anlamına geldiğinden O(V^2) sürer.
Sık karşılaştırılanlar
İlgili sayfalar
- ÇizgeVeri Yapıları, s. 8Çizge, kenarlarla bağlı düğümlerden (köşelerden) oluşan ve yollar, arkadaşlıklar ve bağımlılıklar gibi ilişkileri modellemekte kullanılan bir veri yapısıdır.
- KuyrukVeri Yapıları, s. 24Kuyruk, öğeleri ilk giren ilk çıkar (FIFO) sırasıyla saklayan bir veri yapısıdır; en uzun süre bekleyen öğe her zaman çıkarılacak sonraki öğedir.
- Derinlik Öncelikli AramaVeri Yapıları, s. 11Derinlik öncelikli arama, bir yolu gidebildiği kadar izleyip sonra geri dönerek sıradaki ziyaret edilmemiş dalı keşfeden bir çizge gezinme algoritmasıdır.
- AğaçVeri Yapıları, s. 2Ağaç, kenarlarla bağlı düğümlerden oluşan hiyerarşik bir veri yapısıdır; en üstte tek bir kök düğüm ve altında dallanan çocuk düğümler bulunur.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
- AlgoritmaProgramlamanın Temelleri, s. 1Algoritma, bir listeyi sıralamak ya da en kısa yolu bulmak gibi bir sorunu çözmek veya bir işi tamamlamak için izlenen, sonlu ve adım adım yönergeler bütünüdür.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin