Урок 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)
... # добавить соседей в очередь
visited не даёт ходить по кругу: знакомые могут знать друг друга;popleft() — это BFS, а pop() — обход в глубину, уже другая история;graph.get(node, []) — если у узла нет знакомых, ничего не добавится.Проверка даёт граф graph и имя start. Напишите bfs и напечатайте вершины
в порядке обхода.
Обход в ширину держит очередь (deque) и множество visited.
На каждом шаге берём из начала (popleft), пропускаем уже виденное,
иначе печатаем узел, добавляем его в visited и ставим в конец очереди
всех соседей. Соседей берут через graph.get(node, []).