Поиск в глубину с метками времени. Классификация рёбер[править | править вики-текст]

Поиск в глубину с метками времени. Порядок выбора рёбер — слева направо.

Для каждой из вершин установим два числа — «время» входа  и «время» выхода .

Модифицируем процедуру DFS так.

1. Увеличиваем «текущее время» на 1. .

2. Перекрашиваем вершину  в серый цвет.

3. Для всякой вершины , смежной с вершиной  и окрашенной в белый цвет, выполняем процедуру DFS(w).

4. Перекрашиваем вершину  в чёрный цвет.

5. Увеличиваем «текущее время» на 1. .

Считаем, что граф ориентированный. Очевидно, для любой вершины . Просматриваемые на шаге 3 дуги u→v могут быть:

• . В момент выполнения шага 3 (обозначенный как t) вершина v белая. В таком случае мы для вершины v исполняем DFS, а дуга называется дугой дерева поиска.

• . В момент t вершина v чёрная, сравнениеentry говорит, что в v попали из u. Такая дуга называется прямой.

• . В момент t вершина v также чёрная, но сравнение entry говорит, что в v попали в обход u. Такая дуга называется перекрёстной.

• . В момент t вершина v серая. Имеем дело собратной дугой.

Рёбра неориентированного графа могут быть рёбрами дерева и обратными, но не прямыми и перекрёстными.^[3] Чтобы различать рёбра неориентированного графа, достаточно указанных выше трёх- или двухцветных отметок. Ребро, идущее в белую вершину,— ребро дерева. В серую (чёрную в двухцветном варианте) — обратное. В чёрную — такого не бывает.^[4]

Алгоритм Косарайю требует сортировки вершин в обратном порядке по времени выхода. Метка входа и типы рёбер нужны в алгоритмах поискаточек сочленения и мостов.

Применение[править | править вики-текст]

Поиск в глубину ограниченно применяется как собственно поиск, чаще всего на древовидных структурах: когда расстояние между точками малó, поиск в глубину может «плутать» где-то далеко.

Зато поиск в глубину — хороший инструмент для исследования топологических свойств графов. Например:

• В качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент.

• В топологической сортировке.

• В различных расчётах на графах. Например, как часть алгоритма Диница поиска максимального потока.

13