Код Middle Графы: BFS и DFS обновлено
Обход графа в ширину
Условие
Граф задан списком смежности (объект вершина → массив соседей). Верни массив вершин в порядке обхода в ширину от start.
Примеры
bfsOrder({"a":["b","c"],"b":["d"],"c":["d"],"d":[]}, "a") // ["a", "b", "c", "d"]
bfsOrder({"a":[]}, "a") // ["a"]
bfsOrder({"a":["b"],"b":["a"]}, "a") // ["a", "b"]
Как подойти
BFS даёт кратчайший путь по числу рёбер в невзвешенном графе. Пометка при добавлении в очередь - неочевидная, но важная деталь: пометка при извлечении приводит к дублям и экспоненциальному росту очереди на плотных графах.
Подсказки: 2
- Помечай вершину посещённой при добавлении в очередь, а не при извлечении.
- Иначе одна вершина попадёт в очередь несколько раз.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.