Выбор ответа Junior Графы: BFS и DFS спрашивают часто обновлено
Кратчайший путь без весов
Вопрос
Нужно найти минимальное число переходов между двумя вершинами в графе без весов. Какой обход?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: BFS. BFS обходит вершины в порядке возрастания расстояния от старта, поэтому первое посещение вершины даёт кратчайший путь.
Варианты ответа
- DFS
- BFSправильный ответ
- Дейкстра обязательно
- Топологическая сортировка
Разбор
BFS обходит вершины в порядке возрастания расстояния от старта, поэтому первое посещение вершины даёт кратчайший путь. O(V + E).
- DFS находит какой-то путь, но не обязательно кратчайший.
- Дейкстра тоже даст ответ, но с кучей это O((V + E) log V); без весов это лишнее.
- Топосортировка для ориентированных ациклических графов и порядка зависимостей.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.