← Все уроки

Урок 12.9

Графы: обход в ширину

▶ Теория

Граф — это вершины и связи между ними. Хранить его удобно словарём: у каждого человека — список знакомых.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node in visited:
            continue
        visited.add(node)
        print(node)
        ...                       # добавить соседей в очередь

Проверка даёт граф graph и имя start. Напишите bfs и напечатайте вершины в порядке обхода.

Подсказка

Обход в ширину держит очередь (deque) и множество visited.

На каждом шаге берём из начала (popleft), пропускаем уже виденное, иначе печатаем узел, добавляем его в visited и ставим в конец очереди всех соседей. Соседей берут через graph.get(node, []).