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

Разница — в порядке обхода и в структуре данных под капотом.

BFS (в ширину) идёт «кругами»: сначала все соседи стартовой вершины, потом соседи соседей и т.д. Использует очередь. Главный плюс — находит КРАТЧАЙШИЙ путь в невзвешенном графе (по числу рёбер).

DFS (в глубину) ныряет по одной ветке до упора, потом откатывается и идёт по следующей. Использует стек (или рекурсию). Удобен для проверки связности, поиска циклов, топологической сортировки.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()      # очередь -> FIFO
        print(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                queue.append(nb)

Запомни связку: BFS = очередь = кратчайший путь; DFS = стек/рекурсия = обход вглубь.

Короткая шпаргалка: нужен кратчайший путь в невзвешенном графе — BFS. Просто обойти всё / найти цикл / топосорт — DFS. Под капотом BFS = очередь, DFS = стек.

BFS — очередь, DFS — стек.

BFS всегда находит кратчайший путь в любом графе, поэтому он лучше DFS.