ЯсноПонятно24

Алгоритм поиска в ширину (BFS) используется для обхода или поиска в графе или дереве. Он начинает с вершины и постепенно расширяется на все смежные вершины на текущем уровне перед переходом к вершинам следующего уровня.

Шаги алгоритма поиска в ширину:

1. Создать очередь для хранения вершин, которые нужно посетить.
2. Поместить начальную вершину в очередь.
3. Пометить начальную вершину как посещенную.
4. Пока очередь не пуста:
   • Извлечь вершину из очереди.
   • Посетить все смежные с ней вершины, которые еще не были посещены.
   • Пометить эти вершины как посещенные и добавить их в очередь.
5. Повторять шаг 4, пока очередь не станет пустой.

Пример:

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

def bfs(graph, start):
    visited = set()
    queue = [start]
    
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited:
            print(vertex)
            visited.add(vertex)
            queue.extend([v for v in graph[vertex] if v not in visited])

bfs(graph, 'A')

В данном примере алгоритм начинает с вершины 'A' и посещает все смежные вершины на каждом уровне перед переходом к следующему уровню.