Поиск в глубину (depth-first search)

Один из методов систематического обхода вершин графа называется поиском в глубину. Стратегия поиска в глубину, как следует из ее названия, состоит в том, чтобы идти "вглубь" графа, насколько это возможно. При выполнении поиска в глубину исследуются все ребра, выходящие из вершины, открытой последней, и покидает вершину, только когда не остается неисследованных ребер — при этом происходит возврат в вершину, из которой была открыта вершина v. Этот процесс продолжается до тех пор, пока не будут открыты все вершины, достижимые из исходной. Если при этом остаются неоткрытые вершины, то одна из них выбирается в качестве новой исходной вершины и поиск повторяется уже из нее. Этот процесс повторяется до тех пор, пока не будут открыты все вершины.

Когда вершина v открывается в процессе сканирования списка смежности уже открытой вершины и, процедура поиска записывает это событие, устанавливая поле предшественника v prev[v] равным u. В отличие от поиска в ширину, где подграф предшествования образует дерево, при поиске в глубину подграф предшествования может состоять из нескольких деревьев, так как поиск может выполняться из нескольких исходных вершин.

Как и в процессе выполнения поиска в ширину, вершины графа раскрашиваются в разные цвета, свидетельствующие о их состоянии. Каждая вершина изначально белая, затем при открытии (discover) в процессе поиска она окрашивается в серый цвет, и по завершении (finish), когда ее список смежности полностью сканирован, она становится черной. Такая методика гарантирует, что каждая вершина в конечном счете находится только в одном дереве поиска в глубину.

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

Формальное описание     [вверх]

DFS(G) 
1 for (Для) каждой вершины u є V[G) 
2      do color [u] «- WHITE 
3 	   prev[u] «- NIL 
4 time «— О 
5 for (Для) каждой вершины u Е V[G] 
6      do if color[u] = white 
7         then DFS_Visit(u) 

DFS_Visit(u) 
1 color[u] «— GRAY                    // Открыта белая вершина u
2 time «— time+1 
3 d[u] «— time 
4 for (Для) каждой вершины v є Adj[u] // Исследование ребра (u, v). 
5      do if color [v] = white 
6      then prev[v] «— u 
1           DFS_Visit(v) 
8 color [u] «— BLACK                  // Завершение 
9 f[u] «— time «— time +1 

В строках 1-3 все вершины окрашиваются в белый цвет, а их поля тг инициализируются значением nil. В строке 4 выполняется сброс глобального счетчика времени. В строках 5-7 поочередно проверяются все вершины из V, и когда обнаруживается белая вершина, она обрабатывается при помощи процедуры DFS_Visit. Каждый раз при вызове процедуры DFS_Visit(u) в строке 7, вершина и становится корнем нового дерева леса поиска в глубину. При возврате из процедуры DFS каждой вершине и сопоставляются два момента времени — время открытия (discovery time) d [u] и время завершения (finishing time) f[u].

При каждом вызове DFS_Visit(ix) вершина и изначально имеет белый цвет. В строке 1 она окрашивается в серый цвет, в строке 2 увеличивается глобальная переменная time, а в строке 3 выполняется запись нового значения переменной time в поле времени открытия d [u]. В строках 4-7 исследуются все вершины, смежные с u, и выполняется рекурсивное посещение белых вершин. При рассмотрении в строке 4 вершины v є Adj [и], мы говорим, что ребро (u, v) исследуется (explored) поиском в глубину. И наконец, после того как будут исследованы все ребра, покидающие u, в строках 8-9 вершина и окрашивается в черный цвет, а в поле f[u] записывается время завершения работы с ней.

Оценка сложности     [вверх]

Циклы в строках 1-3 и 5-7 процедуры DFS выполняются за время o(V), исключая время, необходимое для вызова процедуры DFS_Visit. Процедура DFS_VISIT вызывается ровно по одному разу для каждой вершины v є V, так как она вызывается только для белых вершин, и первое, что она делает, — это окрашивает переданную в качестве параметра вершину в серый цвет. В процессе выполнения DFS_Visit(v) цикл в строках 4-7 выполняется |Adj [v]| раз. Поскольку

общая стоимость выполнения строк 4-7 процедуры DFS_Visit равна o(Е).

Время работы процедуры DFS, таким образом, равно o(V + Е).

Пример     [вверх ]

Порядок обхода дерева в глубину:

Граф и остовное дерево, полученное при обходе его вершин методом поиска в глубину:

Визуализатор для алгоритма обхода в глубину.