Kenglik bo'yicha qidirish algoritmi nima?

Keng kengaytirish algoritmi (BFS - Breadth-First Search) daraxt yoki grafda yurish yoki qidirish algoritmidir. U ildiz tugundan (yoki graf daraxt emasligi holda tasodifiy tugundan) boshlanadi va uning barcha to'g'ridan-to'g'ri qo'shnilarini o'rganadi, so'ngra bu qo'shnilarning qo'shnilarini va shunday davom etadi, daraja darajasiga. BFS navbatdan foydalanib amalga oshiriladi.

Ishlash prinsipi:

1. Boshlang'ich tugunni navbatga qo'yish.
2. Navbat bo'sh bo'lmaguncha:
   • Tugunni navbatdan chiqarish.
   • Agar tugun qidirilayotgan bo'lsa, qidirishni to'xtatish.
   • Aks holda, uning barcha ko'rilmagan qo'shnilarini navbatga qo'yish va ularni ko'rilgan deb belgilash.

Xususiyatlar:

• To'liq: Agar mavjud bo'lsa, yechim topilishini kafolatlaydi.
• Optimal: Og'irligi bo'lmagan graflarda eng qisqa yo'lni topadi (kengaytirilganlarining og'irligi teng).
• Vaqt murakkabligi: Graflarning tuzilishiga bog'liq, E ta qirra va V ta tugun uchun — O(V + E).
• Xotira murakkabligi: Eng yomon holatda O(V), chunki ko'rilgan tugunlar va navbatni saqlash kerak.

QA'da qo'llanilishi:

• Sinov ssenariylarida tugunlar orasidagi eng qisqa yo'lni topish.
• Yakuniy avtomatlar testlari davomida tizimning barcha erishiladigan holatlarini o'rganish.
• Crawling davomida veb-saytning barcha sahifalariga kirish imkoniyatini tekshirish.

Misol (daraxtni yurish):

from collections import deque

# Dastlabki ko'rsatkich sifatida daraxtni qo'shni ro'yxat sifatida ifodalash
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)

# Misol uchun chaqirish
# bfs(graph, 'A')
# Natija:
# A
# B
# C
# D
# E
# F