Комбинаторные алгоритмы для программистов



             

Поиск в глубину


При решении многих задач, касающихся ориентированных графов, необходим эффективный метод систематического обхода вершин и дуг орграфов. Таким методом является метод поиск в глубину. Метод поиска в глубину является основой многих эффективных алгоритмов работы с графами. Предположим, что есть ориентированный граф

G
, в котором первоначально все вершины помечены меткой "
unvisited
". Поиск в глубину начинается с выбора начальной вершины
v
орграфа
G
, для этой вершины метка "
unvisited
" меняется на метку "
visited
". Затем для каждой вершины, смежной с вершиной
v
и не посещаемой раньше, рекурсивно применяется поиск в глубину. Когда все вершины, которых можно достичь из вершины
v
, будут рассмотрены, поиск заканчивается. Если некоторые вершины остались не посещенными, то выбирается одна из них и алгоритм повторяется. Этот процесс продолжается до тех пор, пока не будут обойдены все вершины орграфа
G
.

Метод получил свое название - поиск в глубину, поскольку поиск не посещенных вершин идет в направлении вглубь до тех пор, пока это возможно. Например, пусть

x
является последней посещенной нами вершиной. Выбираем очередную дугу
(x,y)
(ребро), выходящую из вершины
x
. Возможна следующая альтернатива: вершина
y

помечена меткой "

unvisited
"; вершина
y

помечена меткой "

visited
". Если вершина
y
уже посещалась, то отыскивается другая вершина, смежная с вершиной
x
; иначе вершина
y
метится меткой "
visited
" и поиск начинается заново от вершины
y
. Пройдя все пути, которые начинаются в вершине
y
, возвращаемся в вершину
x
, то есть в ту вершину, из которой впервые была достигнута вершина
y
. Затем процесс повторяется, то есть продолжается выбор нерассмотренных дуг, исходящих из вершины
x
, и так до тех пор, пока не будут исчерпаны все эти дуги.




Содержание    Вперед