Поиск в глубину

 

Поиск в глубину является обобщением метода обхода дерева в прямом порядке. Предположим, что есть ориентированный граф G, в котором первоначально все вершины помечены как непосещенные. Поиск в глубину начинается с выбора начальной вершины v графа G, и эта вершина помечается как посещенная. Затем для каждой вершины, смежной с вершиной v и которая не посещалась ранее, рекурсивно применяется поиск в глубину. Когда все вершины, которые можно достичь из вершины v, будут «удостоены» посещения, поиск заканчивается. Если некоторые вершины остались не посещенными, то выбирается одна из них и поиск повторяется. Этот процесс продолжается до тех пор, пока обходом не будут охвачены все вершины орграфа G.

Этот метод обхода вершин орграфа называется поиском в глубину, поскольку поиск непосещенных вершин идет в направлении вперед (вглубь) до тех пор, пока это возможно. Например, пусть x – последняя посещенная вершина. Для продолжения процесса выбирается какая-либо нерассмотренная дуга x ® y, выходящая из вершины x. Если вершина y уже посещалась, то ищется другая вершина, смежная с вершиной x. Если вершина y ранее не посещалась, то она помечается как посещенная и поиск начинается заново от вершины y. Пройдя все пути, которые начинаются в вершине y, возвращаемся в вершину x, то есть в ту вершину, из которой впервые была достигнута вершина y. Затем продолжается выбор нерассмотренных дуг, исходящих из вершины x, и так до тех пор, пока не будут исчерпаны все эти дуги.

Для представления вершин, смежных с вершиной v, можно использовать список смежных, а для определения вершин, которые ранее посещались, – массив Visited:

 

 

Graph: TAdjacencyList;

Visited: array[1..n] of boolean;

 

 

Чтобы применить эту процедуру к графу, состоящему из n вершин, надо сначала присвоить всем элементам массива Visited значение false, затем начать поиск в глубину для каждой вершины, помеченной как false.

 

 

procedure DepthSearch(v: integer);

begin

Visited[v] := true;

for каждой вершины y, смежной с v do

if not Visited[y] then

DepthSearch(y);

end;

begin

while есть непомеченные вершины do begin

v := любая непомеченная вершина;

DepthSearch(v);

end;

end.

 

 

Листинг 5.4 – Поиск в глубину

 

Листинг 5.5 – Поиск в глубину

 

 

Как и при поиске в ширину, обнаружив (впервые) вершину v, смежную с и,
мы отмечаем это событие, помещая в поле [v] значение и. Получается дерево -
или несколько деревьев, если поиск повторяется из нескольких вершин. Говоря
дальше о поиске в глубину, мы всегда будем предполагать, что так и дела-
ется (поиск повторяется). Мы получаем подграф предшествования (predecessor
subgraph), определённый так: , где

 

 

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

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

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

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

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

 

d[u] < f[u]

 

Вершина и будет БЕЛОЙ до момента d[u], СЕРОЙ между d[u] и f[u] и ЧЁРНОЙ
после f[u].

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

 

Рисунок 5.2 – Поиск в глубину

 

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

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

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