Алгоритми киҷоии ҷустуҷӯ дар паҳноӣ чист?

Алгоритми ҷустуҷӯ дар паҳлӯ (BFS - Breadth-First Search) алгоритми убур ё ҷустуҷӯ дар дарخت ё граф мебошад. Он аз нодҳои реша (ё ноде тасодуфӣ агар граф дарخت набошад) оғоз ёфта, ҳамаи ҳамсояҳои мустақимро меомӯзад, баъд ҳамсояҳои ин ҳамсояҳоро ва ҳамин тариқ, сатҳ ба сатҳ меомӯзад. BFS бо истифода аз навбат амалӣ мешавад.

Принсипи кор:

1. Нодро оғозӣ дар навбат гузоред.
2. То даме ки навбат холӣ набошад:
   • Нодро аз навбат хориҷ кунед.
   • Агар нод ноде ки ҷустуҷӯ мешавад бошад, ҷустуҷуро боздоред.
   • Дар акси ҳол, ҳамаи ҳамсояҳои нодро, ки то ҳол наомӯхтаанд, ба навбат гузоред ва онҳоро ҳамчун диданшуда нишон диҳед.

Хусусиятҳо:

• Пурра: Гарант медиҳад, ки ҳалли вуҷуд дорад, агар вуҷуд дошта бошад.
• Оптималӣ: Дар графи бе вазн (ки дар он вазни канорҳо баробар аст) кӯтоҳтарин роҳро меёбад.
• Масъулият дар вақт: Аз сохтори граф вобаста аст, барои E канор ва V нуқта — O(V + E).
• Масъулият дар хотира: O(V) дар ҳолати бадтарин, зеро бояд нуқтаҳои диданшударо ва навбатро нигоҳ доред.

Барномаҳо дар QA:

• Ҷустуҷӯ кардани кӯтоҳтарин роҳ байни нуқтаҳо дар сценарийҳои санҷишӣ.
• Таҳқиқи ҳамаи ҳолатҳои дастрас системавӣ дар вақти санҷишҳои автоматӣ.
• Санҷиши дастрасии ҳамаи саҳифаҳои вебсайт дар вақти crawling.

Масалан (гузариш дар дарахт):

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