иск повторяется из нескольких вершин. Говоря дальше о поиске в глубину, мы всегда предполагаем, что так и делается (поиск повторяется). Мы получаем подграф предшествования (predecessor subgraph), определённый так: Gv = (V,EV), где

Подграф предшествования представляет собой лес поиска в глубину (depth-first forest), состоящий из деревьев поиска в глубину (deep-first trees).

Алгоритм поиска в глубину также использует цвета вершин. Каждая из вершин вначале белая. Будучи обнаруженной (discovered), она становится серой; она станет чёрной, когда будет полностью обработана, то есть когда список смежных с ней вершин будет просмотрен. Каждая вершина попадает ровно в одно дерево поиска в глубину, так что эти деревья не пересекаются.

Помимо этого, поиск в глубину ставит на вершинах метки времени (timestamps). Каждая вершина имеет две метки: в d[v] записано, когда эта вершина была обнаружена (и сделана серой), а в f[v] - когда была закончена обработка списка смежных с v вершин (и v стала чёрной).

Эти метки времени используются во многих алгоритмах на графах и полезны для анализа свойств поиска в глубину.

В приводимой далее процедуре DFS (Depth-First Search - поиск в глубину) метки времени d[v] и f[v] являются целыми числами от 1 до 2\V\; для любой вершины и выполнено неравенство

Вершина и будет белой до момента d[u], серой между d[u] и f[u] и чёрной после /[и].

Исходный граф может быть ориентированным или неориентированным. Переменная time - глобальная переменная текущего времени, используемого для пометок.

DFS$(G)$

1for (для) всех вершин $u\in V[G]$

2\hspace{lcm} do $color[u]\leftarrow$ белый

3\hspace{2cm> $\pi[u]\leftarrow NIL$

4$time\leftarrow 0$

5for (для) всех вершин $u\in V[G]$

6\hspace{lcm} do if $color[u]=$ белый

7\hspace{2cm> then DFS-Visit$(u)$

DFS-Visit(u)

1 $color[u]\leftarrow$ белый вершина $u$ была белой

Еж = {(тгН, v) : v е Va,ndir[v] ф NIL}

d[u] < f[u]

Рис. 23.3 23.4 Исполнение алгоритма DFS для ориентированного графа. После просмотра каждое ребро становится либо серым (если оно включается в дерево поиска) или пунктирным (обратные рёбра помечены буквой В (back), перекрёстные - буквой С (cross), прямые - буквой F (forward)). У каждой вершины показаны времена начала и конца обработки.

2$d[u]\leftarrow time\leftarrow time+l$

3\textsc{for} (для) всех $v\in Adj[u]$ обработать ребро $(u,v)$

4\hspace{lcm} \textsc{do if} $color[v]=$ белый

5\hspace{2cm} \textsc{then} $\pi[v]\leftarrow u$

6\hspace{3cm} DFS-Visit$(v)$

7$color[u]\leftarrow$ ч\"~~а5рный вершина обработана, делаем е\"~~а5 чер!

8$f[u]\leftarrow time\leftarrow time+l$

На рис. 23.4 показана работа процедуры DFS на графе рис. 23.2.

В строках 1-3 все вершины красятся в белый цвет; в поле 7г помещается nil. В строке 4 уставливается начальное (нулевое) время. В строках 5-7 вызывается процедура DFS-Visit для всех вершин (которые остались белыми к моменту вызова - предыдущие вызовы процедуры могли сделать их чёрными). Эти вершины становятся корнями деревьев поиска в глубину.

В момент вызова DFS-Visit(m) вершина и - белая. В строке 1 она становится серой. В строке 2 время её обнаружения заносится в d[u] (до этого счётчик времени увеличивается на 1). В строках 3-7 просматриваются смежные с и вершины; процедура DFS-Visit вызывается для тех из них, которые оказываются белыми к моменту вызова. После просмотра всех смежных с и вершин мы делаем вершину и чёрной и записываем в f[u] время этого события.

Подсчитаем общее число операций при выполнении процедуры DFS. Циклы в строках 1-3 и 5-7 требуют О(С) времени (помимо вызовов DFS-Visit). Процедура DFS-Visit вызывается ровно один раз для каждой вершины (ей передаётся белая вершина, и она сразу же делает её серой). Во время выполнения DFS-Visit(u) цикл в строках 3-6 выполняется Аф[и] раз. Поскольку

\Adj[v]\ = Q(E),

vEV

время выполнения строк 3-6 процедуры DFS-Visit составляет ©(E). В сумме получается время ©(С + Е). Свойства поиска в глубину.

Прежде всего отметим, что подграф предшествования (составленный из деревьев поиска в глубину) в точности соответствует структуре рекурсивных вызовов процедуры DFS-Visit. Именно, и = ir[v] тогда и только тогда, когда произошёл вызов DFS-Visit(u) во время просмотра списка смежных с и вершин.

Рис. 23.4 23.5 Свойства поиска в глубину, (а) Результат поиска (в обозначениях рис. 23.4). (Ь) Промежутки между обнаружением и окончанием обработки для каждой из вершин, изображённые в виде прямоугольников. Стрелки указывают структуру деревьев посика в глубину, (с) Отмечены рёбра исходного графа с указанием их типов (рёбра дерева и прямые рёбра ведут вниз, обратные ведут вверх).

Другое важное свойство состоит в том, что времена обнаружения и окончания обработки образуют правильную скобочную структуру (parenthesis structure). Обозначая обнаружение вершины и открывающийся скобкой с пометкой и, а окончание её обработки - закрывающейся с той же пометкой, то перечень событий будет правильно построенным выражением в том смысле (скобки с одинаковыми пометками считаем парными). Например, поиску в глубину на рис. 23.5 (а) соответствует расстановка скобок, изображённая на рисунке 23.5(b).

Чтобы доказать эти и другие свойства, мы должны рассуждать по индукции. При этом, доказывая требуемое свойство рекурсивной процедуры DFS-Visit, мы предполагаем, что рекурсивные вызовы этой процедуры обладают выбранным свойством.

Убедимся вначале, что вызов DFS-Visit(m) для белой вершины и делает чёрной эту вершину и все белые вершины, доступные из неё по белым путям (в которых все промежуточные вершины также белые), и оставляет серые и чёрные вершины без изменений.

В самом деле, рекурсивные вызовы в строке 6 выполняются лишь для белых вершин, являющихся смежными с и. Если какая-то вершина w была закрашена в ходе этих вызовов, то (по индуктивному предположению) она была доступна по белому пути из одной из белых вершин, смежных с и, и потому доступна по белому пути из и.

Напротив, если вершина w доступна по белому пути из и, то этот она доступна по белому пути из какой-то белой вершины v, смежной с и (посмотрим на первый шаг пути). Будем считать, что v - первая из таких вершин (в порядке просмотра в строке 3). В этом случае все вершины белого пути из v в w останутся белыми к моменту вызова DFS-Visit(u), поскольку они недоступны по белым путям из предшествующих v вершин (иначе w была бы также доступна). По индуктивному предположению w станет чёрной после вызова DFS-Visit(u).

Кроме того, сама вершина и станет сначала серой, а потом чёрной. (Заметим, что мы могли бы сразу сделать её чёрной, поскольку программа никак не различает серые и чёрные вершины, однако это различие нам пригодится в дальнейшем.)

Ясно также, что цвета серых и чёрных вершин остаются без изменений (поскольку это верно для рекурсивных вызовов по индуктивному предположению).