Процедура поиска в глубину
Поиск в глубину - вероятно, наиболее важная ввиду многочисленности
приложений стратегия обхода графа. Идея этого метода - идти вперед
в неисследованную область, пока это возможно, если же вокруг все
исследовано, отступить на шаг назад и искать новые возможности для
продвижения вперед. Метод поиска в глубину известен под разными
названиями, например, "бэктрекинг", "поиск с
возвращением".
Понятия новой, открытой, закрытой и активной вершин для поиска в глубину
имеют такой же смысл, как и для поиска в ширину. Отметим, что всегда
имеется не более чем одна активная вершина.
Обход начинается с посещения заданной стартовой вершины $$a$$,
которая
становится активной и единственной открытой вершиной. Затем выбирается
инцидентное вершине $$a$$ ребро $$(a,y)$$ и посещается
вершина $$y$$.
Она становится открытой и активной. Заметим, что при поиске
в ширину вершина $$a$$ оставалась активной до тех пор, пока
не были исследованы все инцидентные ей ребра. В дальнейшем, как и при
поиске в ширину, каждый очередной шаг начинается с выбора активной вершины
из множества открытых вершин. Если все ребра, инцидентные активной
вершине $$x$$, уже исследованы, она превращается в закрытую.
В противном случае
выбирается одно из неисследованных ребер $$(x,y)$$, это ребро
исследуется. Если вершина $$y$$ новая, то она посещается
и превращается в открытую.
Главное отличие от поиска в ширину состоит в том, что при поиске в глубину
в качестве активной выбирается та из открытых вершин, которая была
посещена последней. Для реализации такого правила выбора наиболее удобной
структурой хранения множества открытых вершин является стек: открываемые
вершины складываются в стек в том порядке, в каком они открываются,
а в качестве активной выбирается последняя вершина. Схематически это показано
на рис. 5.1.
(рис 5.1) Обозначим стек для открытых вершин через $$S$$, остальные
обозначения
сохраняют тот же смысл, что и в предыдущем разделе. Через $${\rm
top}(S)$$
обозначается верхний элемент стека (т.е. последний элемент, добавленный
к стеку). Тогда процедура обхода одной компоненты связности методом поиска
в глубину со стартовой вершиной $$a$$ может быть записана следующим
образом (DFS - Depth First Search).
Procedure DFS(a)
посетить вершину $$a$$
$$a\Rightarrow S$$
while $$S\ne
\varnothing$$ do
$$x :={\rm top}(S)$$
if имеется неисследованное
ребро $$(x,y)$$
then исследовать ребро $$(x,y)$$
if вершина $$y$$ новая
then посетить
вершину $$y$$
$$y\Rightarrow S$$
else удалить $$x$$ из $$S$$
Еще раз обратим внимание на основное отличие этой процедуры от аналогичной
процедуры поиска в ширину. При поиске в ширину вершина, став активной,
остается ею, пока не будет полностью исследована ее окрестность, после
чего она становится закрытой. При поиске в глубину, если в окрестности
активной вершины $$x$$ обнаруживается новая вершина $$y$$,
то $$y$$ помещается в стек и при следующем повторении цикла while станет активной. При этом $$x$$ остается в стеке и через какое-то
время снова станет активной. Иначе говоря, ребра, инцидентные
вершине $$x$$, будут исследованы не подряд, а с перерывами.
Алгоритм обхода всего графа - тот же, что и в случае поиска в ширину
(алгоритм 1 предыдущей лекции), только нужно очередь заменить стеком, а процедуру BFS - процедурой DFS.
Свойства 1 и 2 поиска в ширину, отмеченные в предыдущем разделе,
сохраняются и для поиска в глубину. Остается верной и оценка трудоемкости $$O(m+n)$$, но ее доказательство требует несколько иных рассуждений,
так
как каждая вершина теперь может становиться активной несколько раз. Однако
каждое ребро рассматривается только два раза (один раз для каждой
инцидентной ему вершины), поэтому в операторе if в строке 5
ветвь then (строки 6-9)
повторяется $$O(m)$$ раз. В этом же
операторе ветвь else (строка 10)
повторяется $$O(n)$$ раз, так
как каждая вершина может быть удалена из стека только один раз. В целом
получается $$O(m+n)$$, причем остаются справедливыми сделанные
в предыдущей лекции замечания об условиях, при которых имеет место эта
оценка.
DFS-дерево
Поиск в глубину можно применить для нахождения компонент связности графа
или для построения каркаса точно таким же образом, как поиск в ширину.
Понятия прямого и обратного ребра определяются так же, как в предыдущем
разделе и так же доказывается, что прямые ребра при поиске в глубину
образуют каркас графа. Для связного графа каркас, получаемый поиском
в глубину, называется DFS-деревом. DFS-дерево рассматривается
как корневое дерево с корнем в стартовой вершине $$a$$. Это дерево
обладает особыми свойствами, на использовании которых основаны
многочисленные применения метода поиска в глубину. Рассмотрим наиболее
важное из этих свойств.
Относительно любого корневого остовного дерева все ребра графа, не
принадлежащие дереву, можно разделить на две категории. Ребро назовем продольным, если одна из его
вершин является предком другой, в противном
случае ребро назовем поперечным. В примере на рис. 5.2 ребра каркаса выделены жирными линиями, корень - черным кружком.
Обратные ребра показаны
тонкими линиями, из них продольными
являются ребра $$(1, 7)$$, $$(2, 9)$$, $$(3, 8)$$,
а поперечными - ребра $$(1, 2)$$, $$(2, 5)$$, $$(3, 5)$$.
(рис 5.2) Теорема 1. Пусть $$G$$ - связный граф, $$T$$ - DFS-дерево графа $$G$$. Тогда относительно $$T$$ все обратные ребра являются продольными.
Доказательство. Убедимся сначала, что после того, как стартовая
вершина $$a$$ помещена в стек, на каждом последующем шаге работы
алгоритма последовательность вершин, хранящаяся в стеке, образует путь
с началом в вершине $$a$$, а все ребра этого пути принадлежат дереву.
Вначале это, очевидно, так. В дальнейшем всякий раз, когда новая
вершина $$y$$ помещается в стек, к дереву добавляется прямое ребро $$(x,y)$$,
причем вершина $$x$$ находится в стеке перед вершиной $$y$$.
Значит, если указанное свойство имело место до добавления вершины в стек,
то оно сохранится и после добавления. Удаление же вершины из стека,
конечно, не может нарушить этого свойства.
Пусть теперь $$(x,y)$$ - обратное ребро. Каждая из
вершин $$x$$
и $$y$$ в ходе работы алгоритма когда-либо окажется в стеке.
Допустим, $$x$$ окажется там раньше, чем $$y$$.
Рассмотрим шаг алгоритма, на
котором $$y$$ помещается в стек. В этот момент $$x$$ еще
находится
в стеке. Действительно, вершина исключается из стека только тогда, когда
в ее окрестности нет непосещенных вершин. Но непосредственно перед
помещением в стек вершина $$y$$ является новой и принадлежит
окрестности вершины $$x$$. Таким образом, вершина $$x$$
лежит на
пути, принадлежащем дереву и соединяющем вершины $$a$$
и $$y$$.
Но это означает, что вершина $$x$$ является предком вершины $$y$$
в дереве $$T$$ и, следовательно, ребро $$(x,y)$$ -
продольное.
Таким образом, каркас, изображенный на рис. 5.2, не мог быть построен методом поиска в глубину. Кстати, он не мог быть построен и с помощью поиска в ширину (почему?).
Глубинная нумерация
Ввиду важности этого метода опишем еще два варианта алгоритма поиска
в глубину. Первый из них - рекурсивный, и, как обычно, рекурсия дает
возможность представить алгоритм в наиболее компактной форме. Для того
чтобы алгоритм выполнял какую-то полезную работу, будем нумеровать вершины
в том порядке, в каком они встречаются при обходе. Номер, получаемый
вершиной $$x$$, обозначается через $$Dnum (x)$$ и
называется ее глубинным номером.
Вначале полагаем $$Dnum (x)=0$$
для всех $$x$$.
Это нулевое значение сохраняется до тех пор, пока вершина не становится
открытой, в этот момент ей присваивается ее настоящий глубинный номер.
Таким образом, нет необходимости в какой-либо специальной структуре для
запоминания новых вершин - они отличаются от всех других нулевым
значением $$Dnum$$. Переменная $$c$$ хранит текущий номер.
Рекурсивная
процедура DFSR обходит одну компоненту связности, а алгоритм 1 обходит
весь граф и присваивает вершинам глубинные номера.
Алгоритм 1. Поиск в глубину с вычислением
глубинных
номеров - рекурсивный вариант
for $$x\in V$$ do $$Dnum\left(x\right)
:=0$$
$$c:=0$$
for $$x\in V$$ do
if $$Dnum\left(x\right)=0$$ then $$DFSR(x)$$
Procedure $$DFSR(x) $$
$$c:=c+1$$
$$Dnum(x):=c$$
for $$y\in V(x)$$ do
if $$Dnum(y)=0$$ then $$DFSR(y)$$
Построение каркаса
Следующий вариант алгоритма поиска в глубину отличается тем, что не
использует стека для хранения открытых вершин. Стек нужен для того, чтобы
в момент, когда окрестность активной вершины $$x$$ исследована и
необходимо сделать "шаг назад", можно было определить вершину, в
которую
нужно вернуться. Но это та вершина, которая является отцом
вершины $$x$$ в DFS-дереве. Поэтому, если решение
задачи предусматривает построение
DFS-дерева, то это дерево можно использовать и для организации
"возвратных
движений" в процессе обхода. Описываемый ниже алгоритм строит каркас
произвольного графа, каждая компонента связности этого каркаса является
DFS-деревом соответствующей компоненты связности графа. Через $$F(x)$$ обозначается отец вершины $$x$$ в этом
DFS-дереве, при этом для корня дерева (стартовой вершины) $$a$$
полагаем $$F(a)=a$$. Здесь и далее в описаниях алгоритмов
инструкция "открыть (закрыть) вершину" означает, что вершина
каким-то
образом помечается как открытая (закрытая).
Алгоритм 2. Поиск в глубину с
построением каркаса
пометить все вершины как новые
for $$a\in V$$ do
if вершина $$a$$
новая then $$DFST(a)$$
Procedure $$DFST(a)$$
$$F(a)\, :=a$$
открыть вершину $$a$$
$$x\, :=a$$
while $$x$$
открытая do
if имеется неисследованное
ребро $$(x,y)$$
then исследовать
ребро $$(x,y)$$
if вершина $$y$$ новая
then $$F(y):=x$$
открыть вершину $$y$$
$$x:=y$$
else закрыть вершину $$x$$
$$x:=F(x)$$
Шарниры
В качестве примера задачи, для эффективного решения которой можно
использовать основное свойство DFS-дерева, выражаемое теоремой 1,
рассмотрим задачу выявления шарниров в графе. Напомним, что шарниром
называется вершина, при удалении которой увеличивается число компонент
связности. Отсутствие поперечных ребер относительно DFS-дерева позволяет
очень просто узнать, является ли стартовая вершина $$a$$ (корень
этого дерева) шарниром.
Лемма 1. Стартовая вершина а является шарниром графа тогда и
только тогда, когда ее степень в DFS-дереве больше $$1$$.
Доказательство. Если вершину $$a$$ удалить из дерева, то оно
распадется на поддеревья, называемые ветвями. Число ветвей равно степени
вершины $$a$$ в дереве. Так как поперечных ребер нет, то вершины из
разных ветвей не могут быть смежными в графе и каждый путь из одной ветви
в другую обязательно проходит через вершину $$a$$. Следовательно,
если
степень вершины $$a$$ в DFS-дереве больше 1, то эта вершина -
шарнир. Если же степень вершины $$a$$ в DFS-дереве равна 1, то
в дереве имеется единственная вершина $$b$$, смежная
с $$a$$,
и каждая из остальных вершин графа соединена
с вершиной $$b$$ путем, не
проходящим через $$a$$. Поэтому в данном случае удаление
вершины $$a$$
не нарушает связности графа и эта вершина не является шарниром.
Это свойство корня DFS-дерева можно было бы использовать для выявления
всех шарниров, просто выполнив $$n$$ раз поиск в глубину, стартуя
поочередно в каждой вершине. Оказывается, все шарниры можно выявить
однократным поиском в глубину. Следующая теорема характеризует все
шарниры, отличные от корня DFS-дерева. Напомним, что каждая вершина дерева
является и предком, и потомком самой себя. Предок (потомок) вершины,
отличный от самой этой вершины, называется собственным предком (потомком).
Теорема 2. Пусть $$T$$ - DFS-дерево графа $$G$$ с корнем $$a$$.
Вершина $$x\ne a$$ является шарниром графа тогда
и только тогда, когда у нее в дереве $$T$$ имеется такой
сын $$y$$, что ни один потомок вершины $$y$$ не
соединен ребром ни с одним собственным предком вершины $$x$$.
Доказательство. Если $$y$$ - сын вершины $$x$$ и ни один
потомок вершины $$y$$ не соединен ребром ни с одним собственным
предком вершины $$x$$, то, ввиду отсутствия поперечных ребер, любой
путь, соединяющий вершину $$y$$ с корнем, проходит
через $$x$$.
Следовательно, в этом случае вершина $$x$$ - шарнир. Если же для
каждого сына $$y$$ вершины $$x$$ имеется ребро, соединяющее
вершину $$y$$ с каким-либо собственным предком
вершины $$x$$, то
каждый сын вершины $$x$$ соединен с корнем дерева путем, не
проходящим
через $$x$$. Поэтому при удалении вершины $$x$$ граф
останется связным и $$x$$ в этом случае не является шарниром.
Для применения этого критерия к поиску шарниров введем на множестве вершин
функцию $$\Low$$, связанную с DFS-деревом: значением $$\Low(x)$$
является наименьший из глубинных номеров вершин, смежных с потомками
вершины $$x$$. Если вершина $$y$$ является сыном
вершины $$x$$,
то $$\Low(y)\le Dnum(x)$$ (так как вершина $$y$$ является
потомком
самой себя и смежна с вершиной $$x$$ ). Из теоремы 2 следует, что
вершина $$x$$, отличная от $$a$$, является шарниром тогда
и только
тогда, когда у нее имеется сын $$y$$ такой, что $$\Low(y)=Dnum(x).$$
Функцию $$\Low$$ можно определить рекурсивно - если мы
знаем ее
значения для всех сыновей вершины $$x$$ и глубинные номера всех
вершин, смежных с $$x$$ и не являющихся ее сыновьями, то $$\Low(x)$$ есть минимум из всех этих величин, то есть
$$\Low(x)=\min \left(\min_{y \in A} \Low(y),\quad \min_{y\in B}
Dnum(y)\right)\!,$$
где $$A$$ обозначает множество всех сыновей вершины $$x$$,
а $$B$$ - множество всех остальных вершин, смежных
с $$x$$. Нетрудно
видеть, что это определение эквивалентно первоначальному. Исходя из него,
можно вычислять значения функции $$\Low$$ в процессе поиска в
глубину
с помощью следующей рекурсивной процедуры. Предполагается, что вначале всем
элементам массива $$Dnum$$ присвоены нулевые значения.
Procedure $$ComputeLow(x)$$
$$c:=c+1$$
$$Dnum(x):=c$$
$$\Low(x):=c$$
for $$y\in V(x)$$ do
if $$Dnum(y)=0$$
then ComputeLow( $$y$$ )
$$\Low(x):=\min (\Low(x),\Low(y))$$
else $$\Low(x):=\min
(\Low(x),Dnum(y))$$
