Genişlik üzrə axtarış alqoritmi nədir?

Genişlik əvvəlcədən axtarış (BFS - Breadth-First Search) ağac və ya qrafda keçid və ya axtarış algoritmidir. O, kök düyündən (və ya qraf ağac deyilse, hər hansı bir düyündən) başlayır və onun bütün birbaşa qonşularını araşdırır, sonra bu qonşuların qonşularını və s., səviyyə səviyyə. BFS, növbə istifadə edilərək həyata keçirilir.

İş prinsipi:

Başlanğıc düyünü növbəyə qoyun.
Növbə boş olmadığı müddətcə:
- Düyünü növbədən çıxarın.
- Əgər düyün axtarılan düyündürsə, axtarışı dayandırın.
- Əks halda, onun bütün ziyarət olunmamış qonşularını növbəyə qoyun və onları ziyarət olunmuş kimi işarələyin.

Xüsusiyyətlər:

Tamlıq: Əgər mövcuddursa, həll tapılmasını təmin edir.
Optimalik: Çəki olmayan qrafda ən qısa yolu tapır (kənarların çəkisi bərabərdir).
Zaman mürəkkəbliyi: Qrafın quruluşundan asılıdır, E kənar və V düyün üçün — O(V + E).
Yaddaş mürəkkəbliyi: Ən pis halda O(V), çünki ziyarət olunmuş düyünlər və növbə saxlanmalıdır.

QA-da tətbiqlər:

Test ssenarilərində düyünlər arasında ən qısa yolu tapmaq.
Sonlu avtomatların testləri zamanı sistemin bütün əlçatan vəziyyətlərini araşdırmaq.
Crawler zamanı veb saytın bütün səhifələrinə əlçatanlığı yoxlamaq.

Nümunə (ağacın keçidi):

from collections import deque

# Ağacın qonşuluq siyahısı kimi təmsilatı nümunəsi
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)

# Nümunə çağırış
# bfs(graph, 'A')
# Nəticə:
# A
# B
# C
# D
# E
# F