Реализуйте обходы графа в ширину (BFS) и в глубину (DFS). Чем они отличаются и когда какой выбирать?
Короткий ответ
- BFS идёт слоями через очередь, DFS — вглубь через стек или рекурсию
- Множество посещённых обязательно — иначе циклы зацикливают обход
- В BFS помечать вершину при добавлении в очередь, не при извлечении
- BFS находит кратчайший путь в невзвешенном графе
- DFS — для циклов, компонент, топологической сортировки, backtracking
- Оба за O(V + E) времени и O(V) памяти
- Рекурсивный DFS ограничен глубиной стека
Оба обхода работают за O(V + E) времени и O(V) памяти; BFS даёт кратчайшие пути по рёбрам, DFS удобен для структурных задач.
Как сказать вслух
пример ответаBFS я реализую очередью: достаю вершину, добавляю непосещённых соседей, и так слой за слоем. DFS — рекурсией или явным стеком, он уходит вглубь до упора. Выбор простой: нужен кратчайший путь по числу рёбер — BFS, нужно исследовать структуру, циклы или топологический порядок — DFS.
Подробный ответ
Основной ответ
Граф задан списками смежности. BFS: кладём старт в очередь и в множество посещённых; в цикле извлекаем вершину, обрабатываем, добавляем непосещённых соседей, помечая их в момент добавления — пометка при извлечении допускает дубли в очереди и раздувает её. Обход идёт по слоям расстояния, поэтому первое достижение вершины — кратчайший путь по рёбрам; дистанции удобно хранить рядом с пометкой. DFS: рекурсивно посещаем вершину и запускаемся от непосещённых соседей, либо итеративно с явным стеком — важно для глубоких графов, где лимит рекурсии Python (около 1000) достижим. Оба обхода — O(V + E) времени, O(V) памяти. Типичные применения: BFS — кратчайший путь в лабиринте, уровни дерева; DFS — поиск циклов, компоненты связности, топологическая сортировка, backtracking.
Ключевые моменты
- Момент пометки в BFS. Вершина помечается при добавлении в очередь; пометка при извлечении позволяет одной вершине попасть в очередь многократно.
- BFS и кратчайший путь. Слои очереди соответствуют расстоянию от старта, поэтому BFS корректен для кратчайших путей только при одинаковом весе рёбер; со взвешенными нужен Дейкстра.
- Рекурсия vs стек. Рекурсивный DFS читабелен, но падает на глубоких графах; итеративная версия с явным стеком эквивалентна и безопасна.
- Представление графа. Списки смежности дают O(V + E); матрица смежности превращает обход в O(V^2) и оправдана только на плотных графах.
Практический контекст
Обходы — фундамент большинства графовых задач интервью: острова в матрице, кратчайший путь в лабиринте, расписание курсов. Интервьюер смотрит, не забыли ли вы visited, правильно ли выбран момент пометки и можете ли вы обосновать выбор BFS/DFS под задачу. Уточните: ориентированный ли граф, связный ли (возможно, обход нужно запускать из каждой непосещённой вершины), заданы ли рёбра списком или матрицей.
Пример кода
from collections import deque
def bfs(graph, start):
seen, order = {start}, []
q = deque([start])
while q:
v = q.popleft()
order.append(v)
for u in graph.get(v, []):
if u not in seen:
seen.add(u) # пометка при добавлении
q.append(u)
return order
def dfs(graph, v, seen=None, order=None):
if seen is None:
seen, order = set(), []
seen.add(v)
order.append(v)
for u in graph.get(v, []):
if u not in seen:
dfs(graph, u, seen, order)
return order
g = {1: [2, 3], 2: [4], 3: [4], 4: [1]}
assert bfs(g, 1) == [1, 2, 3, 4]
assert dfs(g, 1) == [1, 2, 4, 3]Частые ошибки
- Забывают множество посещённых и зацикливаются на первом же цикле графа
- В BFS помечают вершину при извлечении из очереди — вершины дублируются, память растёт
- Берут DFS для кратчайшего пути в невзвешенном графе, где корректен именно BFS