Кеңдик боюнча издөө алгоритми эмне?

Кеңейтүү биринчи издөө алгоритми (BFS - Breadth-First Search) — бул дарак же графда өтүү же издөө алгоритми. Ал түпкү түйүндөн (же граф дарак эмес болсо, кез келген түйүндөн) баштап, анын бардык түздөн-түз көршүлөрүн изилдейт, андан кийин ошол көршүлөрдүн көршүлөрүн жана ошондой эле улантат, деңгээл боюнча. BFS кезек колдонуу менен ишке ашырылат.

Ишке ашыруу принциби:

1. Баштапкы түйүндү кезекке салыңыз.
2. Кезек бош эмес болгончө:
   • Түйүндү кезектен чыгарыңыз.
   • Эгер түйүн издөөдө болсо, издөөнү токтотуңуз.
   • Болбосо, анын бардык көрбөгөн көршүлөрүн кезекке салыңыз жана аларды көрүлгөн деп белгилеңиз.

Мүнөздөмөлөр:

• Толуктук: Эгер бар болсо, чечим табылуусун кепилдейт.
• Оптималдык: Бейтаң салмактуу графда эң кыска жолду табат (жолдун салмактары бирдей).
• Убакытттык татаалдык: графтын түзүлүшүнө көз каранды, E кыры жана V чокусу үчүн — O(V + E).
• Эстутум татаалдык: О(V) эң жаман учур, анткени көрүлгөн чокулары жана кезек сакталат.

QAда колдонмолор:

• Тест сценарийлеринде түйүндөр аралыгындагы эң кыска жолду издөө.
• Жабык автоматтардын системасынын бардык жеткиликтүү абалдарын изилдөө.
• Crawl учурунда веб-сайттын бардык баракчаларынын жеткиликтүүлүгүн текшерүү.

Мисал (ағашты өтүү):

from collections import deque

# Ағашты көрсөтүү үчүн көршү тизмеси катары мисал
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)

# Мисал чакыруу
# bfs(graph, 'A')
# Натыйжа:
# A
# B
# C
# D
# E
# F