BFS (Breadth-First Search) — алгоритм обхода графа, который посещает все узлы текущего уровня перед переходом к следующему.
- Сложность: O(V + E), где V — количество вершин, E — количество рёбер
- Использует очередь для хранения узлов
- Находит кратчайший путь в невзвешенном графе
- Применения:
- Поиск кратчайшего пути
- Level-order обход дерева
- Connected Components
- Проверка двудольности (Bipartite check)
DFS (Depth-First Search) — алгоритм обхода графа, который идет вглубь до конца пути перед возвратом.
- Сложность: O(V + E)
- Использует стек или рекурсию
- Память: O(h), где h — глубина (высота) графа
- Применения:
- Топологическая сортировка
- Обнаружение циклов
- Strongly Connected Components (Tarjan/Kosaraju)
- Backtracking (решение задач типа "путь в лабиринте")
| Характеристика | BFS | DFS |
|---|
| Структура данных | Очередь | Стек/Рекурсия |
| Память | O(w), где w — ширина графа | O(h), где h — глубина графа |
| Кратчайший путь | Да (в невзвешенном графе) | Нет |
| Топологическая сортировка | Нет | Да |
| Обнаружение циклов | Да | Да |
#Практические рекомендации
-
- Нужен кратчайший путь: BFS
- Нужна топологическая сортировка или обнаружение циклов: DFS
- Ограниченная память: DFS (если глубина меньше ширины)
- Неограниченная память: BFS (для поиска кратчайшего пути)
-
- Используйте visited set для предотвращения повторного посещения узлов
- Для больших графов рассмотрите итеративную реализацию DFS вместо рекурсивной
- Для взвешенных графов используйте Dijkstra или A* вместо BFS
-
- BFS:
collections.deque для очереди
- DFS: рекурсия или явный стек с
list
- Для графов используйте adjacency list или matrix в зависимости от плотности графа