BFS против DFS
Вопрос
Чем отличаются BFS и DFS и когда что брать?
Попробуйте сами
Ответьте про себя или вслух, потом откройте ответ и сверьтесь.
Показать ответ и разбор
Коротко
Ответ
BFS идёт волнами через очередь: кратчайший путь в графе без весов, обход по уровням. DFS уходит вглубь через стек или рекурсию: связность, компоненты, циклы, топосортировка, перебор путей. Оба O(V + E).
Разбор
BFS идёт волнами через очередь: кратчайший путь в графе без весов, обход по уровням. DFS уходит вглубь через стек или рекурсию: связность, компоненты, циклы, топосортировка, перебор путей. Оба O(V + E).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.
Предыдущий вопрос
Минимум семестров с учётом пререквизитов
Следующий вопрос
Цикл в ориентированном графе