Объясни BFS и его сложность
Вопрос
Объясни, как работает BFS, почему он находит кратчайший путь в графе без весов и какая у него сложность.
Попробуйте сами
Ответьте вслух за 2 минуты, как на собесе. Потом сверьтесь с тезисами: что прозвучало, а что нет.
Показать ответ и разбор
Коротко
Что должно прозвучать в ответе
Очередь и пометка посещённых при добавлении
Вершины обрабатываются в порядке неубывания расстояния
Первое посещение вершины даёт кратчайшее расстояние
O(V + E) времени и O(V) памяти
Знает, что при весах нужен Дейкстра
Что могут спросить следом
- Как восстановить сам путь?
- Как обойти сетку, где клетки это вершины?
- Что делать, если веса 0 и 1?
Разбор
BFS кладёт стартовую вершину в очередь с расстоянием 0 и помечает посещённой. Пока очередь не пуста, достаёт вершину и добавляет в очередь её непосещённых соседей с расстоянием на 1 больше, сразу помечая их. Очередь FIFO гарантирует, что все вершины на расстоянии d обработаются раньше вершин на расстоянии d + 1, поэтому, когда вершина впервые попадает в очередь, её расстояние минимально. Каждая вершина входит в очередь один раз, каждое ребро просматривается один раз (дважды для неориентированного графа): O(V + E) времени и O(V) памяти. Чтобы восстановить путь, храню родителя каждой вершины и иду от цели назад. В JS очередь делаю массивом с индексом головы, а не shift. Если у рёбер веса, BFS не годится, нужен Дейкстра; для весов 0 и 1 есть 0-1 BFS с деком.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.