Поиск в глубину
При решении многих задач, касающихся ориентированных графов, необходим эффективный метод систематического обхода вершин и дуг орграфов. Таким методом является метод поиск в глубину. Метод поиска в глубину является основой многих эффективных алгоритмов работы с графами. Предположим, что есть ориентированный граф
, в котором первоначально все вершины помечены меткой "
". Поиск в глубину начинается с выбора начальной вершины
орграфа
, для этой вершины метка "
" меняется на метку "
". Затем для каждой вершины, смежной с вершиной
и не посещаемой раньше, рекурсивно применяется поиск в глубину. Когда все вершины, которых можно достичь из вершины
, будут рассмотрены, поиск заканчивается. Если некоторые вершины остались не посещенными, то выбирается одна из них и алгоритм повторяется. Этот процесс продолжается до тех пор, пока не будут обойдены все вершины орграфа
.
Метод получил свое название - поиск в глубину, поскольку поиск не посещенных вершин идет в направлении вглубь до тех пор, пока это возможно. Например, пусть
является последней посещенной нами вершиной. Выбираем очередную дугу
(ребро), выходящую из вершины
. Возможна следующая альтернатива: вершина
помечена меткой "
"; вершина
помечена меткой "
". Если вершина
уже посещалась, то отыскивается другая вершина, смежная с вершиной
; иначе вершина
метится меткой "
" и поиск начинается заново от вершины
. Пройдя все пути, которые начинаются в вершине
, возвращаемся в вершину
, то есть в ту вершину, из которой впервые была достигнута вершина
. Затем процесс повторяется, то есть продолжается выбор нерассмотренных дуг, исходящих из вершины
, и так до тех пор, пока не будут исчерпаны все эти дуги.
Содержание раздела
