Depth-First Search

«Сколько в сетке отдельных островов», «есть ли в графе зависимостей цикл», «в каком порядке собирать пакеты», «расставьте ферзей всеми способами» — здесь не нужен кратчайший путь. Нужно систематически посетить всё, ничего не пропустив и не зациклившись.

Обход в ширину эти задачи тоже решает, но хранит целый слой вершин, а главное — не даёт того, ради чего берут глубину: порядка завершения вершин, из которого выводятся топологическая сортировка, поиск циклов и компоненты.

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

       A
      / \
     B   C
    / \
   D   E

A -> B -> D
       -> E
  -> C

сначала ветка B целиком (D, затем E), и только потом C

Порядок выхода здесь — D, E, B, C, A. Развернув его, получаем A, C, B, E, D — корректную топологическую сортировку: каждая вершина стоит раньше тех, в кого ведут её рёбра.

WHITE, GRAY, BLACK = 0, 1, 2
color = {v: WHITE for v in graph}
order = []

def visit(v):
    color[v] = GRAY              # вершина на текущем пути
    for u in graph[v]:
        if color[u] == GRAY:
            raise CycleFound      # ребро назад -- цикл
        if color[u] == WHITE:
            visit(u)
    color[v] = BLACK             # поддерево пройдено
    order.append(v)              # порядок завершения

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

Серая вершина — это вершина на текущем пути из корня. Ребро в серую вершину означает, что из неё можно дойти до текущей, а из текущей мы только что пришли в неё: получился цикл. Ребро в чёрную вершину цикла не означает — её поддерево уже полностью обработано и вернуться в текущий путь оттуда нельзя. Два цвета вместо трёх этой разницы не различают, и «цикл» находится там, где его нет.

Корректность топологической сортировки следует из того же: вершина становится чёрной только после всех своих потомков, значит в порядке завершения она стоит после них — а в развёрнутом порядке раньше. Если циклов нет, это и есть искомое линейное упорядочение.

• Глубина рекурсии. В Python по умолчанию около тысячи кадров; на цепочке из миллиона вершин нужен явный стек, а не увеличение лимита.
• Два цвета вместо трёх. Ищете цикл — отличайте «на текущем пути» от «уже обработана», иначе цикл найдётся в любом ромбе.
• Родитель в неориентированном графе. Ребро назад в родителя — не цикл; его нужно исключать явно.
• Забытый откат. В переборе с возвратом состояние, изменённое перед рекурсией, обязано восстанавливаться после неё.
• Обход только из одной вершины. Граф может быть несвязным: компоненты ищутся внешним циклом по всем вершинам.

1. Почему для поиска цикла нужны три цвета, а не два?
2. Почему топологическая сортировка — это развёрнутый порядок завершения, а не порядок входа?
3. Неориентированный граф: как отличить ребро в родителя от настоящего цикла?
4. Перебор с возвратом: что произойдёт, если забыть откатить состояние?
5. Цепочка из миллиона вершин: что сломается в рекурсивной реализации и чем её заменить?