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

Обход в ширину (BFS). Начинаем со стартовой вершины, кладём её в очередь. Пока очередь не пуста: достаём вершину, добавляем в очередь всех её непосещённых соседей. Так сначала посещаются все вершины на расстоянии 1, потом на расстоянии 2 и так далее — «волной». Поэтому первый раз, когда BFS дошёл до вершины, он дошёл по кратчайшему пути (по числу рёбер). Запоминая родителя каждой вершины, путь можно восстановить.

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

• найти циклы;
• топологическая сортировка (порядок сборки зависимостей);
• связные компоненты и компоненты сильной связности;
• перебор с возвратом (backtracking) — лабиринты, головоломки.

Общее: оба алгоритма проходят каждую вершину и каждое ребро по разу — O(V + E), и обязаны отмечать посещённые вершины, иначе на графе с циклами зациклятся. Память: BFS хранит «фронт» волны (может быть широким), DFS — путь от корня (может быть глубоким; рекурсия на длинном пути переполнит стек вызовов).

from collections import deque

def shortest_path(graph, start, goal):
    parent = {start: None}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        if v == goal:
            path = []
            while v is not None:
                path.append(v)
                v = parent[v]
            return path[::-1]
        for u in graph[v]:
            if u not in parent:          # посещённые отмечены родителем
                parent[u] = v
                queue.append(u)
    return None