Обход в ширину и кратчайший путь

Обход в ширину (BFS)

BFS (breadth-first search) исследует граф «кругами»: сначала все соседи старта (расстояние 1), потом соседи соседей (расстояние 2) и так далее. Благодаря этому BFS находит кратчайший путь в невзвешенном графе — по числу рёбер. Как и обход дерева по уровням, BFS использует очередь deque.

Кратчайший путь в рёбрах

Чтобы узнать расстояние от старта до каждой вершины, в очереди храним пару «вершина и её дистанция» — или ведём словарьКоллекция пар «ключ → значение»: {"a": 1}. Быстрый доступ по ключу. По-английски dict. dist. Когда впервые доходим до вершины, записанное расстояние и есть кратчайшее: BFS гарантирует, что раньше всех приходит по самому короткому пути.

Вернётся 3: до D нужно пройти три ребра A→B→C→D. BFS аккуратно наращивает расстояние на 1 на каждой волне.

Обнаружение цикла

Частый вопрос: «есть ли в графе циклКонструкция, повторяющая блок кода: for перебирает элементы, while — пока условие истинно.?» Для ненаправленного графа идея такая: запускаем DFS и, если встречаем уже посещённую вершину, которая не является родителем текущей (откуда мы только что пришли), — значит, нашли цикл.

⚠️ Частые ошибки новичков

Ошибка. В BFS добавлять вершину в visited не при помещении в очередь, а при извлечении. Тогда одну вершину можно положить в очередь несколько раз (через разных соседей), и обход замедлится или исказит расстояния. Правильно: помечаем посещённой сразу, как кладём в очередь. Запустите код и сравните.