BFS и DFS простыми словами: обход графа в ширину и глубину на Python
Что такое BFS и DFS, чем отличаются и когда какой применять. Обход графа в ширину и глубину по шагам с реализацией на Python и разбором сложности.
BFS (поиск в ширину) и DFS (поиск в глубину) — два способа обойти все вершины графа или дерева. BFS идёт слоями: сначала все соседи стартовой вершины, потом соседи соседей — поэтому он находит кратчайший путь по числу рёбер и работает на очереди. DFS уходит по одной ветке до упора и только потом возвращается назад — ему нужен стек или рекурсия, а кратчайший путь он не гарантирует.
Коротко
- Поиск в ширину (BFS) — обход графа в ширину, по слоям от старта. Структура данных — очередь (
deque). Даёт кратчайший путь в невзвешенном графе. - Поиск в глубину (DFS) — обход графа в глубину, по одной ветке до конца. Структура данных — стек или рекурсия. Удобен для компонент связности, поиска циклов, топологической сортировки и бэктрекинга.
- Сложность у обоих одинаковая: по времени, до по памяти.
- Как выбрать: нужно «ближайшее» или «минимум шагов» — BFS. Нужно «обойти всё», «есть ли путь», «перебрать варианты» — обычно проще DFS.
- Главная ошибка в обоих алгоритмах — не помечать посещённые вершины или помечать их слишком поздно.
Алгоритмы поиска в глубину (DFS) и поиска в ширину (BFS) являются основными методами обхода графов и деревьев. Эти алгоритмы часто встречаются на собеседованиях и являются фундаментальными инструментами для решения множества задач программирования.
Что такое DFS и BFS?
DFS (Depth-First Search) - алгоритм поиска в глубину, который исследует граф, погружаясь как можно глубже в каждую ветвь, прежде чем возвращаться назад.
BFS (Breadth-First Search) - алгоритм поиска в ширину, который исследует граф послойно, сначала посещая все вершины на расстоянии 1, затем на расстоянии 2 и так далее.
Основные различия
| Характеристика | DFS | BFS |
|---|---|---|
| Структура данных | Стек (или рекурсия) | Очередь |
| Порядок обхода | Глубина приоритет | Уровень за уровнем |
| Память | O(h) где h - высота | O(w) где w - максимальная ширина |
| Применение | Поиск пути, топологическая сортировка | Кратчайший путь, обход по уровням |
| Время | O(V + E) | O(V + E) |
| Кратчайший путь | Не гарантирует | Гарантирует в невзвешенном графе |
| Память в худшем случае | O(V): граф-цепочка, глубина рекурсии равна числу вершин | O(V): «звезда», все вершины разом лежат в очереди |
| Когда вершину помечают посещённой | При входе в вершину (или при извлечении из стека) | При добавлении в очередь |
| Типичные задачи | Компоненты связности, циклы, острова, бэктрекинг | Минимум шагов в лабиринте, обход дерева по уровням, «ближайший X» |
Если запомнить из таблицы одну строку, то первую: замените в коде обхода очередь на стек — и поиск в ширину превратится в поиск в глубину. Всё остальное — следствия порядка, в котором вершины достаются из структуры.
Поиск в глубину (DFS): реализация на Python
Рекурсивная реализация DFS
def dfs_recursive(graph, start, visited=None): """ Рекурсивный поиск в глубину Args: graph: словарь со списками смежности start: начальная вершина visited: множество посещенных вершин """ if visited is None: visited = set() visited.add(start) print(start, end=' ') for neighbor in graph[start]: if neighbor not in visited: dfs_recursive(graph, neighbor, visited) return visited
Итеративная реализация DFS
def dfs_iterative(graph, start): """ Итеративный поиск в глубину с использованием стека Args: graph: словарь со списками смежности start: начальная вершина """ visited = set() stack = [start] while stack: vertex = stack.pop() if vertex not in visited: visited.add(vertex) print(vertex, end=' ') # Добавляем соседей в стек (в обратном порядке для правильного обхода) for neighbor in reversed(graph[vertex]): if neighbor not in visited: stack.append(neighbor) return visited
Поиск в ширину (BFS): реализация на Python
from collections import deque def bfs(graph, start): """ Поиск в ширину с использованием очереди Args: graph: словарь со списками смежности start: начальная вершина """ visited = set() queue = deque([start]) visited.add(start) while queue: vertex = queue.popleft() print(vertex, end=' ') for neighbor in graph[vertex]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return visited
Практические примеры
Пример 1: Простой граф
# Создаем граф в виде списка смежности graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } print("DFS (рекурсивный):") dfs_recursive(graph, 'A') print() print("DFS (итеративный):") dfs_iterative(graph, 'A') print() print("BFS:") bfs(graph, 'A') print()
Возможный вывод:
DFS (рекурсивный): A B D E F C
DFS (итеративный): A B D E F C
BFS: A B C D E F
Пошаговый пример: обход графа в ширину и в глубину
Возьмём тот же граф из шести вершин и пройдём его руками. Так выглядят его рёбра:
A --- B --- D
| |
C E
| |
+- F -+
Обход графа в ширину (BFS) по шагам
Стартуем из A: она сразу помечена и лежит в очереди. На каждом шаге достаём вершину из начала очереди и дописываем в конец её ещё не посещённых соседей.
| Шаг | Достали | Добавили в очередь | Очередь после шага |
|---|---|---|---|
| 1 | A | B, C | B, C |
| 2 | B | D, E | C, D, E |
| 3 | C | F | D, E, F |
| 4 | D | — | E, F |
| 5 | E | — | F |
| 6 | F | — | пусто |
Порядок обхода — A B C D E F. Обратите внимание на шаг 5: у E есть сосед F, но он уже помечен на шаге 3, поэтому второй раз в очередь не попадает.
Вершины выходят из очереди слоями: сначала A (расстояние 0), потом B, C (расстояние 1), потом D, E, F (расстояние 2). Отсюда и главное свойство BFS: первое попадание в вершину — это попадание по кратчайшему пути. Если вместо множества visited хранить словарь расстояний, получим их для всех вершин сразу:
from collections import deque def bfs_distances(graph, start): dist = {start: 0} queue = deque([start]) while queue: vertex = queue.popleft() for neighbor in graph[vertex]: if neighbor not in dist: dist[neighbor] = dist[vertex] + 1 queue.append(neighbor) return dist print(bfs_distances(graph, 'A'))
{'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2}
### Обход графа в глубину (DFS) по шагам
Теперь то же самое итеративным DFS из раздела выше. Вершину берём с вершины стека (в таблице она справа), соседей кладём в обратном порядке, чтобы первым достался первый по списку.
| Шаг | Достали | Положили в стек | Стек после шага |
| --- | --------------------- | --------------- | --------------- |
| 1 | A | C, B | C, B |
| 2 | B | E, D | C, E, D |
| 3 | D | — | C, E |
| 4 | E | F | C, F |
| 5 | F | C | C, C |
| 6 | C | — | C |
| 7 | C (уже была, пропуск) | — | пусто |
Порядок обхода — `A B D E F C`. DFS прошёл цепочку `A → B → D`, упёрся в тупик, вернулся к `B`, ушёл в `E → F → C` — и только там добрался до `C`, хотя она соседка стартовой вершины.
На шагах 5–7 видна особенность итеративной версии: `C` оказалась в стеке дважды, потому что вершина помечается при извлечении, а не при добавлении. Это нормально — проверка `if vertex not in visited` отбрасывает дубликат. Но размер стека из-за этого ограничен числом рёбер, а не вершин.
## Пример 2: Поиск пути между вершинами
```python
def find_path_dfs(graph, start, end, path=[]):
"""
Поиск пути между двумя вершинами с помощью DFS
"""
path = path + [start]
if start == end:
return path
for neighbor in graph[start]:
if neighbor not in path:
new_path = find_path_dfs(graph, neighbor, end, path)
if new_path:
return new_path
return None
def find_shortest_path_bfs(graph, start, end):
"""
Поиск кратчайшего пути между двумя вершинами с помощью BFS
"""
if start == end:
return [start]
visited = set()
queue = deque([(start, [start])])
visited.add(start)
while queue:
vertex, path = queue.popleft()
for neighbor in graph[vertex]:
if neighbor not in visited:
new_path = path + [neighbor]
if neighbor == end:
return new_path
visited.add(neighbor)
queue.append((neighbor, new_path))
return None
# Пример использования
print("Путь DFS от A до F:", find_path_dfs(graph, 'A', 'F'))
print("Кратчайший путь BFS от A до F:", find_shortest_path_bfs(graph, 'A', 'F'))
Применение в задачах
Задача 1: Поиск всех компонент связности
def find_connected_components(graph): """ Поиск всех компонент связности в графе """ visited = set() components = [] for vertex in graph: if vertex not in visited: component = [] dfs_component(graph, vertex, visited, component) components.append(component) return components def dfs_component(graph, vertex, visited, component): """ Вспомогательная функция для поиска компоненты """ visited.add(vertex) component.append(vertex) for neighbor in graph[vertex]: if neighbor not in visited: dfs_component(graph, neighbor, visited, component) # Пример с несвязным графом disconnected_graph = { 'A': ['B'], 'B': ['A'], 'C': ['D'], 'D': ['C'], 'E': [] } print("Компоненты связности:", find_connected_components(disconnected_graph))
Задача 2: Обход дерева по уровням
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def level_order_traversal(root): """ Обход дерева по уровням (BFS для деревьев) """ if not root: return [] result = [] queue = deque([root]) while queue: level_size = len(queue) level_values = [] for _ in range(level_size): node = queue.popleft() level_values.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level_values) return result # Создаем дерево # 1 # / \ # 2 3 # / \ # 4 5 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) print("Обход по уровням:", level_order_traversal(root)) # Вывод: [[1], [2, 3], [4, 5]]
Задача 3: Кратчайший путь в лабиринте (BFS на сетке)
На собеседованиях граф редко дают словарём. Чаще это матрица, где клетка — вершина, а рёбра ведут в четыре соседние клетки. Список смежности строить не нужно: соседей считаем на лету.
from collections import deque def bfs_grid(grid, start): rows, cols = len(grid), len(grid[0]) dist = {start: 0} queue = deque([start]) while queue: r, c = queue.popleft() for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc = r + dr, c + dc if ( 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != '#' and (nr, nc) not in dist ): dist[(nr, nc)] = dist[(r, c)] + 1 queue.append((nr, nc)) return dist grid = [ '..#.', '..#.', '....', ] print(bfs_grid(grid, (0, 0))[(0, 3)]) # 7
Из левого верхнего угла в правый верхний — 7 шагов: стену приходится обходить снизу. На этом же шаблоне держатся заливка области (flood fill) и подсчёт островов — там подойдёт и DFS, потому что расстояния не нужны. Если стартовых клеток несколько («гниющие апельсины», «расстояние до ближайшего нуля»), все их кладут в очередь сразу — это BFS из нескольких источников.
Сложность алгоритмов
Временная сложность
- DFS: O(V + E), где V - количество вершин, E - количество рёбер
- BFS: O(V + E), где V - количество вершин, E - количество рёбер
Пространственная сложность
- DFS: O(h), где h - высота дерева/глубина рекурсии
- BFS: O(w), где w - максимальная ширина уровня
Когда использовать DFS и BFS?
Используйте DFS когда:
- Нужно найти любой путь между вершинами
- Требуется топологическая сортировка
- Решаете задачи с backtracking
- Память ограничена (для узких и глубоких графов)
Используйте BFS когда:
- Нужно найти кратчайший путь (в невзвешенном графе)
- Требуется обход по уровням
- Ищете ближайший элемент к стартовой позиции
- Граф широкий и не очень глубокий
Когда обычного BFS и DFS уже не хватает
Оба обхода — база, из которой вырастают более специальные алгоритмы:
- У рёбер разные веса — BFS перестаёт находить кратчайший путь, нужен алгоритм Дейкстры.
- Веса только 0 и 1 — хватит 0-1 BFS на деке, без кучи.
- Известны и старт, и финиш, а граф огромный — двунаправленный BFS идёт с двух сторон и просматривает намного меньше вершин.
- Нужно расставить вершины так, чтобы зависимости шли раньше зависимых, — это топологическая сортировка: её делают либо DFS, либо BFS-подобным алгоритмом Кана.
Частые ошибки при реализации
1. Забыть пометить вершину как посещенную
# Неправильно - бесконечный цикл def wrong_dfs(graph, start): stack = [start] while stack: vertex = stack.pop() print(vertex) for neighbor in graph[vertex]: stack.append(neighbor) # Нет проверки на посещение! # Правильно def correct_dfs(graph, start): visited = set() stack = [start] while stack: vertex = stack.pop() if vertex not in visited: visited.add(vertex) print(vertex) for neighbor in graph[vertex]: if neighbor not in visited: stack.append(neighbor)
2. Неправильная обработка пустого графа
def safe_bfs(graph, start): if not graph or start not in graph: return [] visited = set() queue = deque([start]) # остальная логика...
3. Помечать вершину в BFS при извлечении, а не при добавлении
Ответ останется правильным, но одна и та же вершина успеет попасть в очередь много раз — от каждого соседа, который увидел её раньше, чем до неё дошла очередь.
from collections import deque def bfs_mark_on_pop(graph, start): visited = set() queue = deque([start]) pushes = 1 while queue: vertex = queue.popleft() if vertex in visited: continue visited.add(vertex) # поздно: вершина уже могла попасть в очередь ещё раз for neighbor in graph[vertex]: if neighbor not in visited: queue.append(neighbor) pushes += 1 return pushes def bfs_mark_on_push(graph, start): visited = {start} queue = deque([start]) pushes = 1 while queue: vertex = queue.popleft() for neighbor in graph[vertex]: if neighbor not in visited: visited.add(neighbor) # помечаем сразу при добавлении queue.append(neighbor) pushes += 1 return pushes # Полный граф на 300 вершин: каждая соединена с каждой n = 300 complete = {i: [j for j in range(n) if j != i] for i in range(n)} print(bfs_mark_on_pop(complete, 0)) # 44851 добавление в очередь print(bfs_mark_on_push(complete, 0)) # 300
На плотном графе или большой сетке это разница между «прошло» и превышением лимита по памяти.
4. Использовать список как очередь
list.pop(0) сдвигает все оставшиеся элементы, то есть стоит , и BFS незаметно становится квадратичным. У deque.popleft() — .
import timeit from collections import deque def drain_list(n): queue = list(range(n)) while queue: queue.pop(0) def drain_deque(n): queue = deque(range(n)) while queue: queue.popleft() print(timeit.timeit(lambda: drain_list(200_000), number=1)) print(timeit.timeit(lambda: drain_deque(200_000), number=1))
При локальном прогоне первая строка — около 2,8 секунды, вторая — около 0,007. Точные цифры зависят от машины, порядок разницы — нет.
5. Рекурсивный DFS на глубоком графе
В Python глубина рекурсии по умолчанию ограничена 1000 вызовов. Граф-цепочка, длинный связный список или сетка 100×100, которую DFS обходит «змейкой», легко её превышают.
import sys chain = {i: [i + 1] for i in range(5000)} chain[5000] = [] print(sys.getrecursionlimit()) # 1000 try: dfs_recursive(chain, 0) except RecursionError as error: print('RecursionError:', error) dfs_iterative(chain, 0) # доходит до конца: печатает все вершины от 0 до 5000
Варианты: переписать на явный стек или поднять лимит через sys.setrecursionlimit. Первый надёжнее: при очень большом лимите интерпретатор может упасть уже без аккуратного исключения.
6. Искать кратчайший путь через DFS
DFS возвращает первый найденный путь, а не самый короткий. На графе из примеров выше это хорошо видно:
print(find_path_dfs(graph, 'A', 'F')) # ['A', 'B', 'E', 'F'] — 3 ребра print(find_shortest_path_bfs(graph, 'A', 'F')) # ['A', 'C', 'F'] — 2 ребра
Если в условии есть слова «минимальное число ходов», «кратчайший», «ближайший» — это почти всегда BFS.
Заключение
DFS и BFS являются фундаментальными алгоритмами, которые должен знать каждый программист. Понимание их различий, особенностей реализации и областей применения поможет вам эффективно решать широкий спектр задач - от простого обхода графов до сложных задач на динамическое программирование.
Практикуйтесь в реализации обоих алгоритмов, изучайте их вариации и применяйте на различных типах задач. Это поможет вам уверенно чувствовать себя на технических собеседованиях и в повседневной разработке.
Дополнительные ресурсы
Частые вопросы
Что такое BFS простыми словами?
BFS (breadth-first search, поиск в ширину) — это обход графа «кругами по воде». Сначала посещаем стартовую вершину, затем всех её соседей, затем соседей этих соседей и так далее. Чтобы соблюдать такой порядок, вершины складывают в очередь: кто раньше найден, тот раньше обработан.
Что такое DFS простыми словами?
DFS (depth-first search, поиск в глубину) — это обход лабиринта: идём по коридору, пока есть куда, в тупике возвращаемся к последней развилке и пробуем следующий поворот. Возврат обеспечивает стек — явный или стек вызовов при рекурсии.
Чем поиск в ширину отличается от поиска в глубину?
Порядком посещения вершин и структурой данных. Поиск в ширину идёт слоями и использует очередь, поэтому находит кратчайший путь по числу рёбер. Поиск в глубину идёт по одной ветке до конца и использует стек; путь он находит, но не обязательно кратчайший. Время работы одинаковое — .
Что быстрее — BFS или DFS?
Асимптотически одинаково: оба алгоритма посещают каждую вершину и просматривают каждое ребро один раз. На практике всё решает задача. Если цель близко к старту, BFS найдёт её раньше. Если цель глубоко, а граф широкий, DFS может добраться быстрее и займёт меньше памяти. Но гарантию кратчайшего пути даёт только BFS.
Как написать алгоритм BFS на Python?
Нужны три вещи: deque из модуля collections в роли очереди, множество visited и цикл while queue. Достаём вершину через popleft(), перебираем соседей, непосещённых сразу помечаем и добавляем в очередь через append(). Полный код — в разделе «Поиск в ширину (BFS): реализация на Python» выше, это около десяти строк.
Работают ли BFS и DFS на взвешенном графе?
Обойти взвешенный граф можно обоими — на достижимость и компоненты связности веса не влияют. А вот кратчайший путь BFS находит только когда все рёбра «стоят» одинаково. Для неотрицательных весов нужен алгоритм Дейкстры, для весов 0 и 1 — 0-1 BFS.