Mediumbfsdfs
Как работает BFS и DFS?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
Обходы графа/дерева. BFS (вширь, по уровням) — через queue, для кратчайшего пути в unweighted graph. DFS (вглубь) — через stack или recursion, для topological sort, cycle detection, components.
from collections import deque
def bfs(start, graph):
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
def dfs(node, visited, graph):
if node in visited:
return
visited.add(node)
for neighbor in graph[node]:
dfs(neighbor, visited, graph)Оба — O(V+E) время, O(V) память. Topological sort — DFS post-order + reverse, или Kahn's algorithm (BFS с indegree). Для directed graph cycle detection — отслеживать in-progress узлы (gray/black coloring).
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.