Genişlik öncelikli arama algoritması nedir?

Genişlik öncelikli arama algoritması (BFS - Breadth-First Search), ağaç veya graf üzerinde gezinme veya arama algoritmasıdır. Kök düğümden (veya grafı ağaç değilse rastgele bir düğümden) başlar ve doğrudan komşularını, sonra bu komşuların komşularını ve böyle devam eder, seviye seviye. BFS, bir kuyruk kullanılarak uygulanır.

Çalışma prensibi:

Başlangıç düğümünü kuyruğa koyun.
Kuyruk boş olmadığı sürece:
- Bir düğüm çıkarın.
- Eğer düğüm aranan düğümse, aramayı durdurun.
- Aksi takdirde, ziyaret edilmemiş tüm komşularını kuyruğa koyun ve onları ziyaret edildi olarak işaretleyin.

Özellikler:

Tamlık: Eğer varsa, çözüm bulunmasını garanti eder.
Optimumluk: Ağırlıksız grafikte en kısa yolu bulur (kenar ağırlıkları eşittir).
Zaman karmaşıklığı: Grafın yapısına bağlıdır, E kenar ve V düğüm için — O(V + E).
Hafıza karmaşıklığı: En kötü durumda O(V), çünkü ziyaret edilen düğümleri ve kuyruğu tutmak gerekir.

QA'da uygulamalar:

Test senaryolarında düğümler arasındaki en kısa yolu bulma.
Sonlu otomata testleri sırasında sistemin ulaşılabilir tüm durumlarını araştırma.
Web sitesinin tüm sayfalarına erişilebilirliği tarama sırasında test etme.

Örnek (ağaç gezinmesi):

from collections import deque

# Bir ağacı komşuluk listesi olarak temsil etme örneği
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    visited.add(start_node)

    while queue:
        node = queue.popleft()
        print(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Örnek çağrı
# bfs(graph, 'A')
# Çıktı:
# A
# B
# C
# D
# E
# F