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

Другой естественный метод поиска узлов, достижимых из s, естественно приме- няется в ситуации, когда граф G действительно представляет собой лабиринт из взаимосвязанных комнат. Вы начинаете от s и проверяете первое ребро, ведущее из него, — допустим, к узлу v. Далее вы следуете по первому ребру, выходящему из , и продолжаете действовать по этой схеме, пока не окажетесь в «тупике» — узле, для которого вы уже исследовали всех соседей.

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

DFS(u):

Пометить узел u как «проверенный» и добавить u в R

Для  каждого  ребра  (u,  v),  инцидентного  u

Если узел v не помечен как «проверенный»

Рекурсивно вызвать DFS(v)

Конец Если Конец цикла

Чтобы применить его для решения задачи связности s–t, достаточно изначально объявить все узлы «непроверенными» и вызвать DFS(s).

Между алгоритмами DFS и BFS существуют как фундаментальное сходство, так и фундаментальные отличия. Сходство основано на том факте, что оба алго- ритма строят компоненту связности, содержащую s, и, как будет показано в сле- дующем разделе, в обоих случаях достигаются сходные уровни эффективности.

Хотя алгоритм DFS в конечном итоге посещает точно те же узлы, что и BFS, обычно посещение происходит в совершенно ином порядке; поиск в глубину проходит по длинным путям и может заходить очень далеко от s, прежде чем вернуться к более близким непроверенным вариантам. Это различие проявляется в том факте, что алгоритм DFS, как и BFS, строит естественное корневое дерево T из компоненты, содержащей s, но обычно такое дерево имеет совершенно иную структуру.

Узел s становится корнем дерева T, а узел u становится родителем v, если u отвечает за обнаружение v. А именно, если DFS(v) вызывается непосред- ственно во время вызова DFS(u), ребро (u, v) добавляется в T. Полученное дерево называется деревом поиска в глубину компоненты R.

На рис. 3.5 изображен процесс построения дерева DFS с корнем в узле 1 для графа на рис. 3.2. Сплошными линиями обозначены ребра T, а пунктирными — ре- бра G, не принадлежащие T. Выполнение алгоритма DFS начинается с построения пути, содержащего узлы 1, 2, 3, 5, 4. Выполнение заходит в тупик в узле 4, в котором найти новые узлы не удается, поэтому алгоритм возвращается к узлу 5, находит узел 6, снова возвращается к 4 и находит узлы 7 и 8.

В этой точке в компоненте связности новых узлов нет, поэтому все незавершенные рекурсивные вызовы DFS завершаются один за другим, а выполнение подходит к концу.

Этот пример дает представление о внешних отличиях деревьев DFS от дере- вьев BFS. Такие деревья обычно получаются узкими и глубокими, тогда как для последних характерны минимально короткие пути от корня до листьев.

Тем не менее, как и в случае BFS, мы можем выдвинуть достаточно сильное утверждение о расположении ребер G, не входящих в дерево, относительно ребер DFS-дерева T: как и показано на схеме, ребра, не входящие в дерево, могут соединять только пред- ков T с потомками.