§ 73. Поиск в глубину

В этом параграфе рассматривается один из методов обхода всех вершин и ребер графа. Этот метод, именуемый поиском в глубину (сокращенно ПГ), послужил основой для разработки ряда быстрых алгоритмов на графах. Один из таких алгоритмов — алгоритм выделения двусвязных компонент графа — приводится в § 74. Дадим вначале некоторые определения. Ориентирован­ий граф D — (V, A) назовем ориентированным деревом корнем r € V,если каждая его вершина достижима из и основание графа D — граф D_b — является деревом. В тех случаях, когда недоразумение исключено, ориентированное дерево с корнем r будем называть просто деревом.

Пусть G — неориентированный связный граф, В про­весе поиска в глубину вершинам графа G присваиваютcя номера (ПГ-номера), а его ребра помечаются. В начале ребра не помечены, вершины не имеют ПГ-номеров. Начинаем с произвольной вершины v₀. Присваиваем ей ПГ-номер ПГ(v₀)=1 и выбираем произвольное ребро v₀w Ребро v₀w помечается как «прямое», а вершина w включает (из v₀) ПГ-номер ПГ(w)=2. После этого переводим в вершину w. Пусть в результате выполнения нескольких шагов этого процесса пришли в вершину х, и Пусть k — последний присвоенный ПГ-номер. Далее действуем в зависимости от ситуации следующим образом.

1. Имеется непомеченное ребро ху. Если у вершины уже есть ПГ-номер, то ребро ху помечаем как «обратное» продолжаем поиск непомеченного ребра, инцидентного вершине х. Если же вершина у ПГ-номера не имеет, то полагаем ПГ(y) = k + 1, ребро ху помечаем как «прямое» : переходим в вершину у. Вершина у считается получив­шей свой ПГ-номер из вершины х. На следующем шаге будем просматривать ребра, инцидентные вершине у.

2. Все ребра, инцидентные вершине х, помечены. В этом случае возвращаемся в вершину, из которой х по­лучила свой ПГ-номер.

Процесс закончится, когда все ребра будут помечены : произойдет возвращение в вершину v₀.

Описанный процесс можно реализовать так, чтобы ремя работы соответствующего алгоритма составляло (/EG/ + /G/).

Такой алгоритм (алгоритм A1) мы сейчас рассмотрим. Пусть граф G задан списками смежности, т. е. N_v — список вершин, инцидентных вершине v, и v₀ — исходная вершина, с которой начинается поиск. В процессе работы алгоритма каждая вершина графа ровно один раз включается в список Q и исключается из него. Вершина включается в этот список сразу после получения ПГ-номера, исключается, как только произойдет возвращение из этой вершины. Включение и исключение вершин производятся всегда с конца списка, т. е. Q — стек. Результат работы алгоритма — четыре списка ПГ, F, Т и В: ПГ(v)— ПГ-номер вершины v; F(v)—имя вершины, из которой вершина v получила свой ПГ-номер; Т и В— соответственно списки ориентированных «прямых» и «об­ратных» ребер графа G. Эти ребра получают ориентацию в процессе работы алгоритма a1. Именно, если ребро ху помечается из вершины х как «прямое», то в Т заносит­ся дуга (х, у), а если — как «обратное», то эта дуга за­носится в В.

АлгоритмA1 поиска в глубину в неориентированном связном графе.

1 ПГ(v):=1, Q(1):= v₀, F(v_o):=0, T:=¢, B:=¢, k:=1,р:=1 [k — последний присвоенный ПГ-номер, р — указатель конца стека Q, т. е. Q(p)— имя последней вершины стека Q].

2. v := Q(p) [v — исследуемая вершина].

3. Просматривая список N_v, найти такую вершину w,что ребро vw не помечено, и перейти к п. 4. Если таких вершин нет, то перейти к п. 5.

4. Если вершина w имеет ПГ-номер, то пометить ребро vw как «обратное» и занести дугу (v, w) в список В. Пе­рейти к п. 3 и продолжить просмотр списка N_v. Иначе k:=k + 1, ПГ(w):=k, F(w):=v, ребро vw пометить как «прямое» и дугу (v, w) занести в список T, р:=р+ 1, Q(p):=w [вершина w получила ПГ-номер и занесена встек Q]. Перейти к п. 2.

5. р := р — 1 [вершина v вычеркнута из Q]. Если р = 0, то конец. Иначе перейти к п. 2.

Корректность алгоритма очевидна. Оценим его трудо­емкость. Каждое включение и исключение вершины из стека Q выполняется за время O(1). Поэтому для всей работы, связанной с изменением стека Q, достаточно вре­мени O (|G|). Каждое выполнение п. 4 требует O (1) вре­мени, и для каждой вершины v € VG этот пункт выпол­няется deg v раз. Поэтому затраты на его выполнение в

целом составят O (∑deg v) = О (|EG|). Суммарное время выполнения п. 3 также составит O(|EG|), если поза­ботиться о том, чтобы каждая вершина списка N_v просма­тривалась только один раз при всех выполнениях данно­го пункта. Этого легко добиться, если, например, ввести такую новую функцию (массив) t, что t(v)—номер пер­вой непросмотренной вершины в списке N_v. Тогда сле­дующий просмотр п. 3 следует начинать с вершины z = N_v(t(v)).

Итак, трудоемкость алгоритма A1 составляет O(|EG|+|G|). Ясно, что это время является наилучшим воз­можным по порядку, так как каждая вершина и каждое ребро графа G должны быть просмотрены хотя бы один раз.

Легко видеть, что требуемый для реализации алго­ритма A1 объем памяти также составляет O(|EG|+|G|).

На рис. 73.1 слева изображены граф G и списки смеж­ности, которыми он задан. Справа представлены резуль­таты применения к этому графу поиска в глубину из

вершины v₀ = 1. «Прямые» ребра проведены сплошными линиями, а «обратные» пунктирными. Каждой вершине приписан ее ПГ-номер.

Из способа построения множеств Т и В непосредствен­но вытекают следующие утверждения.

Утверждение 73.1. Дуги множества Т образуют ориентированное остовное дерево с корнем в вершине v₀. Это остовное дерево часто называют остовным глубин­ным деревом (ОГД). Обозначать

его будем также че­рез Т.

Утверждение 73.2. Если ориентированное ребро (х, у) принадлежит В, то ПГ(х)>ПГ(у), т. е. «обрат­ные» ребра всегда ведут к ранее пройденным вершинам.

Поиск в глубину используется в качестве составной тасти во многих алгоритмах. Отметим одну задачу, решение которой можно получить с помощью алгоритма A1 фазу, почти без дополнительных вычислительных за­трат. Это — задача выделения связных компонент графа. Чтобы решить ее за время O(|EG|+|G|), достаточно один раз просмотреть список вершин графа, выполняя следующие действия. Если просматриваемая вершина v_l имеет ПГ-номер, то перейти к следующей. Иначе — положить v₀ = v_l ПГ(v₀) = k + 1, где k — последний присвоенный ПГ-номер, и применить поиск в глубину.Пос­ле его окончания (т. е. выделения компоненты, содержа­щей v_l) продолжить просмотр списка, перейти к верши­не v_l+1. Различать вершины разных компонент можно, например, по их ПГ-номерам, если для каждой компонен­ты запомнить последний ПГ-номер.