Поиск в глубину в графе
Существует много различных алгоритмов, в основе которых лежит систематический перебор вершин графа, при котором каждая вершина просматривается ровно один раз. Будем рассматривать такие методы обхода или поиска в графе, что:
а) алгоритм решения легко «погружается» в этот метод;
б) каждое ребро графа анализируется число раз, ограниченное константой.
Опишем классический метод поиска в неориентированном графе – метод поиска в глубину(depth first search) (рис. 8.8).
Общая идея следующая. Начинаем поиск с некоторой фиксированной вершины k (корня). Затем выбираем одну из смежных (соединенных ребрами) с ней вершин. Назовем эту вершину u. Далее процесс поиска повторяется от u.
Пусть на каком-то этапе мы находимся в вершине v. Если среди ее соседей есть хотя бы одна новая (еще непросмотренная) вершина w, то просматриваем ее. После этого w перестает быть новой, и дальнейший поиск продолжаем с w.
Если же у вершины v нет ни одной новой «соседки», то говорим, что v использована, и возвращаемся на шаг назад– в вершину, из которой попали в v. Просмотренные, но еще не использованные вершины накапливаются в стеке. Использованные вершины удаляются из стека. Когда стек опустеет, то у связного графа будут просмотрены все вершины, у несвязного – компонента связности, содержащая вершину k.
| |
Рис. 8.8. Поиск в глубину из вершины 1
Вопрос. Когда следует прервать работу алгоритма, если мы ищем путь от 1 до 5? Где находится путь?
Поиск в глубину можно записать с помощью рекурсивной процедуры GL.
Логический массив НОВЫЙ – глобальная переменная.
1 procedure GL(v) {поиск в глубину из вершины v}
2 begin
3 НОВЫЙ[v]:= ложь;
3 for u 
ЗАПИСЬ[v] do {перебор всех соседей v}
4 if НОВЫЙ[u] then GL[u]
5 end; {v использована}
Поиск в глубину в произвольном (необязательно связном) графе проводится согласно следующему алгоритму:
1 begin
2 for v V do НОВЫЙ[v]:= истина ; {инициализация}
3 for v V do {перебор всех вершин графа}
4 if НОВЫЙ[v] then GL(v)
5 end. {поиск окончен, все вершины просмотрены}
Покажем теперь, что этот алгоритм просматривает каждую вершину в точности один раз и сложность его порядка O(n+m).
Первый вызов GL(v) для некоторой вершины v влечет за собой просмотр всех вершин компоненты связности графа, содержащей v. Это обеспечивает цикл 3 процедуры GL: после просмотра v будет вызвана GL для всех ее новых соседей.
Каждая вершина просматривается ровно один раз – просматриваются только новые вершины, сразу после просмотра НОВЫЙ[v]:= ложь.
Гарантия того, что будут просмотрены все вершины – цикл 3 основного алгоритма.
Оценим теперь вычислительную сложность алгоритма.
Циклы 2 и 3 основного алгоритма содержат n шагов, не считая вызовы процедуры GL. Строка 2 процедуры GL для всех вызовов повлечет O(n) шагов. Полное число шагов цикла 3 процедуры GL для всех рекурсивных вызовов будет порядка m – числа всех ребер, так как от вершины к ее соседям мы двигаемся по ребрам.
Суммарная сложность алгоритма О(n+m).
В связи с важностью поиска в глубину для проектирования алгоритмов на графах представим также нерекурсивную версию процедуры GL.
Рекурсия устраняется стандартным способом: каждая просмотренная вершина помещается в СТЕК и удаляется из стека после использования.
1 procedure GL_1(v); {поиск в глубину,начиная с v}
2 begin
3 СТЕК:= NIL; СТЕК <= v; {v помещается в СТЕК}
4 НОВЫЙ[v]:= ложь;
5 while СТЕК do
6 begin
7 verh:= top(СТЕК); {читаем верхний элемент}
{будем искать первую новую «соседку» элемента verh}
8 if НАЧАЛО[verh]=nil then b:= ложь
9 else b:= NOT(НОВЫЙ[НАЧАЛО[verh]^.uzl]);
{НАЧАЛО[verh]^.uzl-номер первой вершины в списке
ЗАПИСЬ[verh]}
10 while b do
11 begin
12 НАЧАЛО[verh]:= НАЧАЛО[verh]^.next;
{переводим указатель НАЧАЛО на следующую запись в
списке ЗАПИСЬ[verh]}
13 if НАЧАЛО[verh]=nil then b:= ложь
14 else b:= NOT(НОВЫЙ[НАЧАЛО[verh]^.uzl])
{проверяем, будет ли вершина следующей записи
новой}
15 end;
16 if НАЧАЛО[verh]=nil then {найдена новая
вершина!}
17 begin
18 verh:= НАЧАЛО[verh]^.uzl;
19 СТЕК <= verh; {новая вершина помещена в СТЕК}
20 НОВЫЙ[verh]:= ложь
21 end
22 else {вершина verh использована}
23 verh <= СТЕК {удалить verh из СТЕКа}
24 end {while СТЕК <> NIL}
25 end; {procedure GL1}
Корректность процедуры GL_1 доказывается аналогично GL.
Ответ.Когда 5 попадет в стек. В стеке.