BFS и DFS простыми словами: обход графа в ширину и глубину на Python

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

16 мин чтенияPython · алгоритмы · графы · DFS · BFS · поиск в глубину · поиск в ширину · рекурсия · собеседование · структуры данных

BFS (поиск в ширину) и DFS (поиск в глубину) — два способа обойти все вершины графа или дерева. BFS идёт слоями: сначала все соседи стартовой вершины, потом соседи соседей — поэтому он находит кратчайший путь по числу рёбер и работает на очереди. DFS уходит по одной ветке до упора и только потом возвращается назад — ему нужен стек или рекурсия, а кратчайший путь он не гарантирует.

Коротко

  • Поиск в ширину (BFS) — обход графа в ширину, по слоям от старта. Структура данных — очередь (deque). Даёт кратчайший путь в невзвешенном графе.
  • Поиск в глубину (DFS) — обход графа в глубину, по одной ветке до конца. Структура данных — стек или рекурсия. Удобен для компонент связности, поиска циклов, топологической сортировки и бэктрекинга.
  • Сложность у обоих одинаковая: O(V+E)O(V + E) по времени, до O(V)O(V) по памяти.
  • Как выбрать: нужно «ближайшее» или «минимум шагов» — BFS. Нужно «обойти всё», «есть ли путь», «перебрать варианты» — обычно проще DFS.
  • Главная ошибка в обоих алгоритмах — не помечать посещённые вершины или помечать их слишком поздно.

Алгоритмы поиска в глубину (DFS) и поиска в ширину (BFS) являются основными методами обхода графов и деревьев. Эти алгоритмы часто встречаются на собеседованиях и являются фундаментальными инструментами для решения множества задач программирования.

Что такое DFS и BFS?

DFS (Depth-First Search) - алгоритм поиска в глубину, который исследует граф, погружаясь как можно глубже в каждую ветвь, прежде чем возвращаться назад.

BFS (Breadth-First Search) - алгоритм поиска в ширину, который исследует граф послойно, сначала посещая все вершины на расстоянии 1, затем на расстоянии 2 и так далее.

Основные различия

ХарактеристикаDFSBFS
Структура данныхСтек (или рекурсия)Очередь
Порядок обходаГлубина приоритетУровень за уровнем
Память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: она сразу помечена и лежит в очереди. На каждом шаге достаём вершину из начала очереди и дописываем в конец её ещё не посещённых соседей.

ШагДосталиДобавили в очередьОчередь после шага
1AB, CB, C
2BD, EC, D, E
3CFD, E, F
4D—E, F
5E—F
6F—пусто

Порядок обхода — 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) сдвигает все оставшиеся элементы, то есть стоит O(n)O(n), и BFS незаметно становится квадратичным. У deque.popleft() — O(1)O(1).

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, поиск в глубину) — это обход лабиринта: идём по коридору, пока есть куда, в тупике возвращаемся к последней развилке и пробуем следующий поворот. Возврат обеспечивает стек — явный или стек вызовов при рекурсии.

Чем поиск в ширину отличается от поиска в глубину?

Порядком посещения вершин и структурой данных. Поиск в ширину идёт слоями и использует очередь, поэтому находит кратчайший путь по числу рёбер. Поиск в глубину идёт по одной ветке до конца и использует стек; путь он находит, но не обязательно кратчайший. Время работы одинаковое — O(V+E)O(V + E).

Что быстрее — BFS или DFS?

Асимптотически одинаково: оба алгоритма посещают каждую вершину и просматривают каждое ребро один раз. На практике всё решает задача. Если цель близко к старту, BFS найдёт её раньше. Если цель глубоко, а граф широкий, DFS может добраться быстрее и займёт меньше памяти. Но гарантию кратчайшего пути даёт только BFS.

Как написать алгоритм BFS на Python?

Нужны три вещи: deque из модуля collections в роли очереди, множество visited и цикл while queue. Достаём вершину через popleft(), перебираем соседей, непосещённых сразу помечаем и добавляем в очередь через append(). Полный код — в разделе «Поиск в ширину (BFS): реализация на Python» выше, это около десяти строк.

Работают ли BFS и DFS на взвешенном графе?

Обойти взвешенный граф можно обоими — на достижимость и компоненты связности веса не влияют. А вот кратчайший путь BFS находит только когда все рёбра «стоят» одинаково. Для неотрицательных весов нужен алгоритм Дейкстры, для весов 0 и 1 — 0-1 BFS.

Потренироваться в спокойной обстановке

Все задачи

Читать дальше

Все статьи
Алгоритмы и структуры данныхДинамическое программирование для начинающих: от нуля до пониманияПошаговое руководство по динамическому программированию с простыми объяснениями, визуализацией и примерами на Python и JavaScript. Разбираем мемоизацию, табуляцию и классические задачи.Алгоритмы и структуры данныхБинарное дерево поиска (BST): поиск, вставка и удаление элемента на PythonБинарное дерево поиска (BST): что это и главное свойство, поиск, вставка и удаление элемента — лист, один потомок, два потомка — по шагам, с кодом на Python и JavaScript и оценкой сложности.Алгоритмы и структуры данныхРекурсия — что это простыми словами, примеры на PythonРекурсия — что это простыми словами: функция вызывает саму себя. Примеры на Python: факториал, Фибоначчи, обход дерева. Глубина рекурсии, RecursionError, рекурсия или цикл, задачи.Алгоритмы и структуры данныхNumber of Islands: подсчёт островов на сетке через DFS, BFS и DSUРазбор Number of Islands: подсчёт компонент на сетке через DFS, BFS и Union-Find, почему рекурсия падает на больших картах и как тот же код решает Max Area of Island и Surrounded Regions.Алгоритмы и структуры данныхОбход бинарного дерева: preorder, inorder, postorder, стек и алгоритм МоррисаТри обхода бинарного дерева в глубину: рекурсия, итеративные версии со стеком, обход Морриса за O(1) памяти и правило, какой порядок выбрать под задачу. Код на Python с проверкой.Алгоритмы и структуры данныхКратчайший и длиннейший путь в DAG: топологическая сортировка за O(V + E)Как найти кратчайший и самый длинный путь в ориентированном ациклическом графе за O(V + E): топологическая сортировка, релаксация рёбер, отрицательные веса, критический путь и связь с ДП.