АЛГОРИТМЫ ПОИСКА НА ГРАФАХ. Рекурсивное прохождение графа в глубину




АЛГОРИТМЫПОИСКА НА ГРАФАХ

 

Рекурсивное прохождение графа в глубину

 

В основе алгоритмов поиска на графах лежит систематический перебор вершин графа, причем каждая вершина просматривается в точности один раз. Рассмотрим вначале метод поиска в неориентированном графе, который стал одной из основных методик проектирования графовых алгоритмов. Этот метод называется поиском в глубину (от англ. 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, состоящий из трех связных компонент (задать самостоятельно).

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-05-16 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: