# Genişlik Öncelikli Arama

Adres: https://softwaredictionary.org/tr/terimler/breadth-first-search
Kategori: Veri Yapıları
Son güncelleme: 2026-09-30
İngilizcesi: Breadth-First Search
Türkçe karşılığı: enine arama
Okunuşu: bredt först sörç

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: Python'da BFS ile her düğüme kaç atlama gerektiğini saymak

```python
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.

---

Software Dictionary: https://softwaredictionary.org/tr · https://softwaredictionary.org/tr/llms.txt