Поиск в глубину (DFS)

Введение

Поиск в глубину (DFS) — один из базовых алгоритмов для работы с графами.

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

Как это работает?

Мы начинаем с одной вершины. После её посещения мы рекурсивно запускаем DFS для каждой смежной вершины, которая ещё не была посещена. Таким образом, мы посещаем все вершины, достижимые из стартовой вершины.

Классификация рёбер графа

При запуске DFS рёбра можно классифицировать, используя времена входа и выхода их концов.

Эта классификация часто полезна в задачах на графы.

Предположим, DFS обрабатывает ребро $(x, y)$.

1. Если вершина $y$ ещё не была посещена

• Древесное ребро — ребро $(x, y)$ называется древесным ребром, если DFS проходит по нему, чтобы посетить $y$ в первый раз.