Поиск
в глубину в неориентированном связном графе.
Источник:
Емеличев В.А., Мельников О.И.,
Саванов В.И., Тышкевич Р.И. Лекции по теории графов – М.: Наука. Гл. ред.
физ.-мат. лит., 1990.
Пусть G – неориентированный связный
граф. В процессе поиска в глубину вершинам графа G присваиваются номера (ПГ –
номера), а его ребра помечаются. В начале ребра не помечены, вершины не имеют
ПГ – номеров. Начинаем с произвольной вершины V0, присваиваем ей ПГ – номер
ПГ(V0) = 1 и выбираем произвольное ребро (V0,W). Ребро (V0,W)
помечается как “прямое”, а вершина W получает (из V0) ПГ –
номер ПГ(W) = 2. После этого переходим в вершину W. Пусть
в результате выполнения нескольких шагов этого процесса пришли в вершину X, и
пусть k – последний присвоенный ПГ – номер. Далее действуем в зависимости от
ситуации следующим образом.
1.
Имеется
непомеченное ребро (X,Y). Если у вершины Y уже
есть ПГ – номер, то ребро (X,Y) помечаем как “обратное” и
продолжаем поиск непомеченного ребра, инцидентного вершине X. Если
вершина Y ПГ – номера
не имеет, то полагаем ПГ(Y) = k + 1, ребро (X,Y)
помечается как “прямое” и переходим в вершину Y. Вершина Y
считается получившей свой ПГ – номер из вершины X. На следующем шаге будем
просматривать ребра, инцидентные вершине Y.
2.
Все
ребра, инцидентные вершине X, помечены. В этом случае
возвращаемся в вершину, из которой x получила свой ПГ – номер.
Процесс закончится, когда все ребра будут помечены и
произойдет возвращение в вершину V0.
Описанный процесс можно реализовать так, чтобы время
работы соответствующего алгоритма составляло O(|EG|+|G|) , где |EG| -
число ребер графа, |G| - число вершин графа.
Пусть граф G задан списками смежности,
т.е. NV – список вершин, инцидентных вершине V, V0 – исходная вершина, с
которой начинается поиск. В процессе работы алгоритма каждая вершина графа
ровно один раз включается в список Q и исключается из него.
Вершина включается в этот список сразу после получения ПГ – номера, и
исключается, как только произойдет возвращение из этой вершины. Включение и
исключение вершин производится всегда с конца списка, т.е. Q –
стек. Результат работы алгоритма – четыре списка ПГ, F, T, B: ПГ(V) – ПГ
– номер вершины V; F(V) – имя вершины, из которой
вершина V получила свой ПГ – номер; T и B – соответственно списки
ориентированных “прямых” и “обратных” ребер графа G. Эти ребра получают
ориентацию в процессе работы алгоритма. Именно, если ребро (X,Y)
помечается из вершины X как “прямое”, то в T
заносится дуга (X,Y), а если как “обратное”, то
эта дуга заносится в B.
Алгоритм поиска в глубину в неориентированном
связном графе
1.
ПГ(V0) :=
1, Q(1):= V0, F(V0) = 0, T := 0, B := 0, k:=1, p:=1 [ k –
последний присвоенный ПГ – номер, p – указатель конца стека Q, т.е. Q(p) –
вершина стека Q].
2. V := Q(p)
3.
Просматривая
список NV, найти такую вершину W, что ребро (V,W) не
помечено, и перейти к п. 4. Если таких вершин нет, то перейти к п. 5.
4.
Если
вершина W имеет ПГ – номер, то пометить ребро (V,W) как
обратное и занести в список B. Перейти к п. 3 и продолжить
просмотр списка NV. Иначе k := k+1, ПГ(W) := k, F(W) := V, ребро
(V,W) пометить как “прямое” и занести в список T, p := p+1, Q(p) := W
[вершина получила ПГ – номер и занесена в стек Q]. Перейти к п. 2.
5.
p := p-1 [вершина v
вычеркнута из Q]. Если p = 0, то конец. Иначе
перейти к п. 2.
