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

Поиск в глубину – это обобщение метода обхода дерева в прямом порядке. Стратегия поиска в глубину такова: идти «вглубь» пока это возможно (есть не пройденные исходящие ребра), и возвращаться и искать другой путь, когда таких ребер нет. Так делается, пока не будут обнаружены все вершины, достижимые из исходной. Если после этого остаются необнаруженные вершины, можно выбрать одну из них и повторить процесс. Делать так до тех пор, пока мы не обнаружим все вершины графа.

Как и при поиске в ширину, обнаружив впервые вершину v, смежную с u, мы отмечаем это событие, помещая в поле массива pi[v] значение u. Получается дерево – или несколько деревьев, если поиск повторяется из нескольких вершин. Каждая вершина попадает ровно в одно дерево поиска в глубину, так что эти деревья не пересекаются. Деревья поиска в глубину образуют лес поиска в глубину.

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

Помимо этого алгоритм ставит на вершинах метки времени. Каждая вершина имеет две метки: в d[v] записано, когда эта вершина была обнаружена и сделана серой, а в f[v] – когда была закончена обработка списка смежных с v вершин и v стала черной. Эти метки используются во многих алгоритмах на графах и полезны для анализа свойств поиска в глубину.

Процедуру, реализующую этот алгоритм, называют DFS(), что является сокращением от depth-first search – поиск в глубину. Time – глобальная переменная текущего времени, используемая для пометок.

1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 14

DFS(GRAPH G) { Vertex u; For (для каждой вершины u графа G) { color[u]=WHITE; /*вершины становятся белыми */ pi[u]=NULL; /* родителем всех вершин считается NULL */ } time=0; For (для каждой вершины u графа G) if (color[u]==WHITE) DFS-Visit(u); } DFS-Visit(vertex u) { vertex v; color[u]=GRAY; d[u]=++time; for(для всех вершин v смежных с u) if (color[v]==WHITE) { pi[v]=u; DFS-Visit(v); } color[u]=BLACK; f[u]=++time; }

В строках 6-7 все вершины красятся в белый цвет, в поле pi помещается NULL. В строке 9 устанавливается начальное нулевое время. В строках 10-12 вызывается процедура DFS-Visit для всех вершин которые остались белыми к моменту вызова. Эти вершины становятся корнями деревьев поиска в глубину. В момент вызова DFS-Visit(u) вершина u – белая. В строке 4 она становится серой. В строке 5 счетчик времени увеличивается на 1 и полученное время заносится в d[u]. В строках 6-11 просматриваются смежные с u вершины; процедура DFS-Visit вызывается для тех из них, которые оказываются белыми к моменту вызова. После просмотра всех смежных с u вершин мы делаем вершину u черной и записываем в f[u] время этого события.

Анализ

Оценим время работы процедуры поиска в ширину. В процессе работы вершины только темнеют, так что каждая вершина кладется в очередь не более одного раза. Следовательно, вынуть ее можно только один раз. Каждая операция с очередью требует О(1) шагов, так что всего на операции с очередью уходит время О(V). Теперь заметим, что список смежных вершин просматривается лишь когда вершина извлекается из очереди, т.е. не более одного раза. Сумма длин всех этих списков равна Е (количеству ребер ориентированного графа) или 2Е (удвоенному количеству ребер неориентированного графа) и всего на их обработку уйдет время О(Е). Инициализация требует О(V) шагов, так что всего получается О(V+Е)=О(max(V,E)). Поскольку Е>V, то часто считают что О(V+Е)=О(Е). Тем самым время работы процедуры BFS() пропорционально размеру представления графа G в виде списков смежных вершин.

Время выполнения алгоритма поиска в глубину такое же, как и у алгоритма поиска в ширину.