Выбор ответа Middle Графы: BFS и DFS обновлено
Когда помечать посещённой в BFS
Вопрос
В BFS вершину помечают посещённой при добавлении в очередь, а не при извлечении. Почему?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Иначе вершина попадёт в очередь много раз, и растут время и память. Если помечать при извлечении, вершину успеют добавить в очередь несколько соседей.
Варианты ответа
- Так требует очередь в JS: повторно добавить элемент в массив нельзя
- Иначе BFS найдёт не кратчайший путь, а первый попавшийся
- Разницы нет: обе пометки дают одинаковую очередь и время
- Иначе вершина попадёт в очередь много раз, и растут время и памятьправильный ответ
Разбор
Если помечать при извлечении, вершину успеют добавить в очередь несколько соседей. Ответ останется верным, но очередь раздуется, в плотном графе до O(E) копий. Пометка при добавлении гарантирует, что каждая вершина в очереди ровно один раз.
- Язык тут ни при чём.
- Кратчайшее расстояние при первом извлечении всё равно корректно.
- Разница есть в производительности.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.