Чем BFS отличается от DFS при обходе графа?

BFS обходит граф слоями через очередь и находит кратчайший путь в невзвешенном графе, а DFS уходит вглубь через стек или рекурсию и удобен для топологических задач.

BFS

• Очередь: сначала старт, затем все вершины на расстоянии 1, потом на расстоянии 2 и так далее.
• Применения: кратчайший путь по числу рёбер, проверка двудольности, «минимальное число ходов».

DFS

• Стек или рекурсия: идём вглубь, пока есть куда, затем откатываемся.
• Применения: топологическая сортировка, поиск циклов, компоненты связности, backtracking.

Общее

• Сложность одинакова: O(V + E), память O(V) на visited.
• Итеративный DFS безопаснее рекурсивного на глубоких графах из-за переполнения стека.

Как выбирать

Ответ близко к старту и ветвление большое — BFS; нужно перебрать всё пространство решений или проверить достижимость — DFS обычно проще и экономнее по памяти.

Коротко для собеседования

BFS идёт по слоям и даёт кратчайший путь по числу рёбер, DFS уходит вглубь и подходит для циклов, топологической сортировки и перебора. Оба работают за O(V + E); на глубоких графах пишите DFS итеративно, чтобы не переполнить стек.