АЛГОРИТМЫПОИСКА НА ГРАФАХ
Рекурсивное прохождение графа в глубину
В основе алгоритмов поиска на графах лежит систематический перебор вершин графа, причем каждая вершина просматривается в точности один раз. Рассмотрим вначале метод поиска в неориентированном графе, который стал одной из основных методик проектирования графовых алгоритмов. Этот метод называется поиском в глубину (от англ. depth first search), или прохождением графа в глубину.
Общая идея этого метода состоит в следующем. Мы начинаем поиск с некоторой фиксированной вершины v0. Затем выбираем произвольную вершину и, смежную с v0, и повторяем наш процесс от u. В общем случае предположим, что мы находимся в вершине v. Если существует новая (еще не просмотренная) вершина u, то мы рассматриваем эту вершину (она перестает быть новой) и, начиная с нее, продолжаем поиск. Если же не существует ни одной новой вершины, смежной с v, то мы говорим, что вершина v использована, возвращаемся в вершину, из которой мы попали в v, и продолжаем процесс (если v = v0, то поиск закончен). Другими словами, поиск из вершины v в глубину основывается на поиске в глубину из всех новых вершин, смежных с v.
На рис. 3.1 показан граф, вершины которого, перенумерованы в соответствии с тем порядком, в котором они просматриваются в процессе поиска в глубину. Жирными линиями выделен маршрут прохождения графа в глубину.
Рис. 3.1. Нумерация вершин графа (в скобках), соответствующая очередности, в которой они просматриваются в процессе поиска в глубину.
Методика поиска в глубину очевидным образом переносится на ориентированные графы. Нетрудно проверить, что в случае ориентированного графа результатом перебора вершин графа будет посещение за O (n+m) шагов всех таких вершин u, что существует путь из v в u.
Рекурсивный алгоритм поиска в графе в глубину
Этот алгоритм можно легко записать с помощью следующей рекурсивной процедуры:
procedure WG (v)
(* прохождение графа в глубину из вершины v; переменные new и G - глобальные *)
Begin
рассмотреть v; new [ v ]:= ложь;
for u Î G [ v ] do if new [ u ] then WG (u)
end; (* вершина v использована*)
Begin
for v Î V do new [ v ]:= истина; (*инициализация*)
for v Î V do if new [ v ] then WG (v)
End.
Нерекурсивное прохождение графа в глубину
В связи с тем, что прохождение в глубину играет важную роль в проектировании алгоритмов на графах, представим также нерекурсивную версию процедуры WG. Рекурсия устраняется стандартным способом при помощи программной реализации стека. Каждая просмотренная вершина помещается в стек и удаляется из стека после использования.
procedure WG1 [ v ];
(* прохождение графа глубину, начиная с вершины v (нерекурсивная версия процедуры WG); массивы P, new и G - глобальные *)
begin СТЕК:= Æ; СТЕК Ü v; рассмотреть v; new [ v ]:= ложь;
while СТЕК ¹Æ do begin
t Ü СТЕК; (* t - верхний элемент стека *)
(*найти первую новую вершину в списке G [ t ] *)
for u Î G [ t ] do
if new [ t ] then begin
СТЕК Ü u; рассмотреть u; new [ t ]:= ложь
End
end;
End.
Алгоритм поиска в графе можно применить для вычисления связных компонент графа. Для этого в качестве рассмотрения вершины v следует ее печатать без перевода на новую строку, а в цикле вызова процедуры в главном блоке печатать какой-нибудь разделитель (например, “Перевод строки”). Тогда после отработки всей программы будут построчно отпечатаны номера вершин всех связных компонент.
Поиск в ширину
Теперь рассмотрим несколько иной метод поиска в графе, называемый поиском в ширину (от англ. breadth first search). Он основан на замене стека очередью: чем раньше посещается вершина (помещается в очередь), тем раньше она используется (удаляется из очереди). Использование вершины происходит с помощью просмотра всех еще не просмотренных соседей этой вершины.
На рис. 3.2 представлен граф, вершины которого занумерованы согласно очередности, в которой они посещаются в процессе поиска в ширину. А жирными линиями выделены проходящие при этом ребра.
Рис. 3.2. Нумерация вершин графа (в скобках), соответствующая очередности, в которой они просматриваются в процессе поиска в ширину.
Как и в случае поиска в глубину, этот метод можно использовать и для ориентированных графов. Очевидно, что тогда посещаются только те вершины, до которых существует путь от вершины, с которой мы начинаем поиск.
Процедура поиска в графе в ширину представлена ниже:
procedure WS (v);
(* поиск в ширину в графе с началом в вершине v; переменные new, G - глобальные *)
Begin
ОЧЕРЕДЬ:= Æ; ОЧЕРЕДЬ Ü v; посетить v; new [ v ]:= ложь
while ОЧЕРЕДЬ ¹Æ do begin
р Ü ОЧЕРЕДЬ; (* вершина p - использована*)
for u Î G [ р ] do
if new [ u ] then begin
ОЧЕРЕДЬ Ü u; new [ u ]:= ложь
End
End
End.
Нетрудно убедиться, что вызов процедуры WS(v) приводит к посещению всех вершин связной компоненты графа, содержащей вершину v, причем каждая вершина просматривается (проходится) в точности один раз. Вычислительная сложность поиска в ширину также O (m + n), так как каждая вершина помещается в очередь и удаляется из очереди в точности один раз, а число итераций основного цикла, очевидно, будет иметь порядок числа ребер графа.
Оба вида поиска в графе - в глубину и в ширину могут быть использованы для нахождения пути между фиксированными вершинами v и u. Достаточно начать поиск с вершины v и вести его до момента посещения вершины u. Преимуществом поиска в глубину является тот факт, что в момент посещения вершины u стек содержит последовательность вершин, определяющую путь из v в u. Это становится очевидным, если отметить, что каждая вершина, помещаемая в стек, является соседом верхнего элемента в стеке. Однако недостатком поиска в глубину является то, что полученный таким образом путь в общем случае не будет кратчайшим путем из v в u.
Поиск с возвратом
Опишем теперь общий метод, позволяющий решить практически любую задачу теории графов и значительно сократить число шагов в алгоритмах типа полного (исчерпывающего) перебора всех возможностей. Чтобы применить этот метод, искомое решение должно иметь вид последовательности á x1,..., xn. ñ Основная идея метода состоит в том, чтобы строить наше решение последовательно, начиная с пустой последовательности (длины 0). Вообще, имея данное частичное решениеá x1,..., xi ñ, мы стараемся найти такое его допустимое расширение xi+1; которое либо можно расширить далее, либо оно уже является решением. Если такого расширения не существует, то мы возвращаемся к нашему частичному решению á x1,..., xi-1 ñ и продолжаем наш процесс на предыдущем шаге ветвления, отыскивая новое, еще не использованное допустимое значение х'i. Отсюда название “алгоритм с возвратом” (англ. backtracking).
Точнее говоря, мы предполагаем, что для каждого k > 0 существует некоторое множество Ak, из которого мы будем выбирать кандидатов для k- й координаты частичного решения. Очевидно, что множества Ak должны быть определены для каждого частичного решения á x1,..., xk ñ. И если Ak ¹ Æ, то расширение возможно.
Этот алгоритм можно записать в виде следующей схемы:
begin k:= 1;
while k > 0 do
if существует еще неиспользованный элемент y Î Ak then begin
х [ k ]:= y; (* элемент y использован *)
if (x [1],..., x [ k ]) является решением then write (x [1],..., x [ k ]);
k:= k + 1
End
else (* возврат на более короткое частичное решение; все элементы множества Ak вновь становятся неиспользованными *)
k:= k - 1
End.
Покажем также вариант рекурсивного алгоритма поиска с возвратом:
procedure АР (k);
(*генерирование всех решений, являющихся расширением последовательности x [1],..., x [ k -1], массив x -, глобальный *)
Begin
for у Î Ak do begin
x [ k ]:= у;
if x [1],..., x [ k ] есть решение then write (x [1],..., x [ k ])
АР (k + 1)
End
End.
Генерирование всех решений можно выполнить вызовом AP (1).
3.5. Лабораторная работа №3: “Прохождение графа”
Цель:
Исследование свойств достижимости и связности вершин в графе, используя алгоритмы поиска в графе.
Задание:
Используя методические указания раздела 3разработать программу поиска всех путей в графе от заданной вершины, используя один из алгоритмов поиска по выбранному варианту.
Варианты выполнения работы:
1) Прохождение графа в глубину с помощью рекурсивного алгоритма.
2) Прохождение графа в глубину нерекурсивным алгоритмом с программной реализацией стека.
3) Прохождение графа в ширину.
Порядок выполнения работы
Работа рассчитана на 2 часа. В результате должна быть разработана исследовательская C - или Pascal -программа, которая должна определять:
· последовательность прохождения графа: список посещенных вершин для каждой связной компоненты;
· список пройденных ребер в каждой связной компоненте.
В качестве тестов для отладки исследовательской программы рекомендуется использовать следующие графы:
1) Связный неориентированный граф из 13 вершин, представленный на рис. 3.1.
2) Неориентированный граф с числом вершин не менее 12, состоящий из трех связных компонент (задать самостоятельно).