Поиск в глубину в графе

Общая идея этого метода состоит в следующем. Мы начинаем поиск с некоторой фиксированной вершины v₀. Затем выбираем произвольную вершину u, смежную с v₀ ( (v₀, u)Е), и повторяем процесс от u. В общем случае предположим, что мы находимся в вершине v. Если существует новая (еще непросмотренная) вершина u, (v, u)Е, то мы рассматриваем эту вершину (она перестает быть новой) и, начиная с нее, продолжаем поиск. Если же не существует ни одной новой вершины, смежной с v, то мы говорим. что вершина v использована, возвращаемся в вершину, из которой мы попали в v, и продолжаем процесс (если v = v₀, то поиск закончен). Таким образом, поиск в глубину из вершины v основывается на поиске в глубину из всех новых вершин, смежных с v.

Этот процесс поиска из вершины v для неориентированного простого графа, заданного списком инцидентности СПИСОК (СПИСОК[v] -список вершин, смежных (инцидентных) с вершиной v) легко описать с помощью следующей рекурсивной процедуры:

1 procedure ПОИСК_В_ГЛУБИНУ_В_ГРАФЕ _G(v)

{поиск в глубину из вершины v;

переменные НОВЫЙ, ЗАПИСЬ - глобальные}

2 begin рассмотреть v; НОВЫЙ[v] := ложь;

3 for uЗАПИСЬ[v] do

4 if НОВЫЙ[u] then ПОИСК_В_ГЛУБИНУ_В_ГРАФЕ _G(u)

5 end {вершина v использована}

Поиск в глубину в произвольном, необязательно связном, неориентированном простом графе проводится по следующему алгоритму:

1 begin

2 for vV do НОВЫЙ[v]:= истина ; {инициализация}

3 for vV do

4 if НОВЫЙ[v] then ПОИСК_В_ГЛУБИНУ_В_ГРАФЕ _G(v)

5 end

Покажем теперь, что этот алгоритм просматривает каждую вершину в точности один раз и его сложность порядка O(n+m). Отметим сначала, что вызов ПОИСК_В_ГЛУБИНУ_В_ГРАФЕ _G(v) влечет за собой просмотр всех вершин связной компоненты графа, содержащей v (если НОВЫЙ[u] = истина для каждой вершины u этой компоненты). Это непосредственно следует из структуры процедуры ПОИСК_В_ГЛУБИНУ_В_ГРАФЕ _G(v): после посещения вершины (строка 2) следует вызов процедуры для всех ее новых соседей. Отметим также, что каждая вершина графа просматривается не более одного раза, так как просматриваться может только вершина v, для которой НОВЫЙ[v] = истина, сразу же после посещения этой вершины исполняется присваивание НОВЫЙ[v] := ложь (строка 2 процедуры).

Рис 3. 3.

На рис. 3.3. показан граф, вершины которого перенумерованы (номера в скобках) в соответствии с тем порядком, в котором они просматриваются в процессе поиска в глубину (мы отождествляем вершины графа с числами 1, ... , 13 и полагаем, что в списке СПИСОК[v] вершины упорядочены по возрастанию).

Алгоритм начинает поиск поочередно от каждой еще не просмотренной вершины, следовательно, просматриваются все вершины графа (необязательно связного).

Чтобы оценить сложность алгоритма, отметим сначала, что число шагов в обоих циклах (строки 2 и 3 алгоритма) порядка n, не считая шагов, выполнение которых инициировано вызовом процедуры ПОИСК_В_ГЛУБИНУ_В_ГРА

ФЕ _G. Эта процедура выполняется не более n раз во втором цикле сразу после посещения каждой вершины для каждого из ее новых соседей, итого суммарно O(n+m) раз. Полное число шагов, выполняемое циклом в строке 3 процедуры ПОИСК_В_ГЛУБИНУ_В_ГРАФЕ _G, для всех вызовов этой процедуры будет порядка m, где m - число ребер. Это дает общую сложность алгоритма O(n+m).

Отметим, что алгоритм поиска в глубину в графе легко модифицировать так, чтобы он вычислял связные компоненты графа.

В связи с тем, что поиск в глубину играет важную роль в проектировании алгоритмов на графах, представляет интерес нерекурсивная версия процедуры ПОИСК_В_ГЛУБИНУ_В_ГРАФЕ _G. Рекурсия устраняется стандартным способом при помощи стека. Каждая просмотренная вершина помещается в стек и удаляется из стека после ее использования.

Метод поиска в глубину очевидным образом переносится на ориентированные графы.