5.2. МЕТОД ПОИСКА В ГЛУБИНУ

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

Поиск в глубину можно также осуществлять и на ориентированном графе. Если граф ориентирован, то, находясь в узле х, мы выбираем ребра только выходящие из х. Исследовав все ребра, выходящие из у, мы возвращаемся в даже тогда, когда в у входят другие ребра, еще не рассмотренные.

Если поиск в глубину осуществляется на связном неориентированном графе, то, как легко показать, посещается каждый узел и исследуется каждое ребро. Если граф несвязен, то отыскивается его связная компонента. Закончив работу с ней, выбирают в качестве нового начального узла узел, который еще не посещался, и начинают новый поиск.

Поиск в глубину на неориентированном графе разбивает ребра, составляющие на два множества Ребро помещается в множество если узел до не посещался до того момента, когда мы, рассматривая ребро оказались в узле у.

Рис. 5.4. Последовательность шагов построения остовного дерева.

Затем рассматривается ребро Оба узла принадлежат одному и тому же множеству Следовательно, из идет путь из ребер, уже вошедших в остовное дерево, и потому не добавляется. Вся последовательность шагов приведена на рис. 5.4. Остовное дерево, получающееся в результате, изображено на рис.

Теорема 5.1. Алгоритм 5.1 находит остовное дерево наименьшей стоимости для связного графа Если в цикле, описанном строками 5—10, рассматривается ребер, то затрачивается время где Следовательно, алгоритм 5.1 занимает не более времени.

Доказательство. Корректность алгоритма вытекает непосредственно из леммы 5.2 и того факта, что строки 8 и 9 сохраняют узлы в том же самом множестве тогда и только тогда, когда

Рис. 5.5. Остовное дерево наименьшей стоимости.

димся в у, а узел помечен как "старый", ибо может оказаться отцом узла

Пример 5.2. Условимся изображать ребра, входящие в сплошными линиями, а ребра из В — штриховыми. Кроме того, корень дерева (начальный узел, выбираемый в строке 8) будем рисовать наверху, а сыновей каждого узла будем располагать слева направо в том порядке, в котором их ребра добавлялись в строке 4 процедуры На рис. показано одно возможнее разбиение графа, изображенного на рис. 5.7,а, на множества древесных и обратных ребер, построенное в процессе поиска в глубину.

Вначале все узлы помечены как "новые". Допустим, что в строке 8 выбирается Выполняя можно в строке 2 взять Так как узел помечен как "новый", добавляем к и вызываем Теперь можно было бы выбрать узел из но он уже помечен как "старый". Тогда выберем Так как "новый" узел, добавляем к и вызываем Каждый узел, смежный с является теперь "старым", так что снова вызываем

Выполняя процедуру находим ребро добавляем его к и вызываем Заметим, что на рис. узел расположен справа от найденного ранее сына узла Никакие "новые" узлы не смежны с так что опять вызываем На этот раз мы не обнаруживаем "новых" узлов, смежных с и потому вызываем Далее находит а находит Все узлы оказываются на дереве, и они помечены как "старые". Таким образом, алгоритм закончит работу. Если бы граф не был связным, то цикл в строках 8, 9 надо было повторить для каждой компоненты.

Теорема 5.2. Алгоритм 5.2 на графе с узлами и ребрами требует шагов.

Рис. 5.7. Граф него остовное дерево, построенное в процессе поиска в глубину.

Доказательство. Строка 7 и поиск "нового" узла в строке 8 требуют шагов, если список узлов составлен и один раз просмотрен. Время, затрачиваемое на если не считать рекурсивных вызовов процедуры самой себя, пропорционально числу узлов, смежных с у. вызывается только один раз для данного у, поскольку после вызова узел у помечается как "старый". Таким образом, всего на ПОИСК тратится время теорема доказана.

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

Лемма 5.3. Если обратное ребро, то либо у — предок узла либо предок узла у в остовном лесу.

Доказательство. Без потери общности будем считать, что у посещается раньше т. е. вызывается раньше, чем Поэтому в тот момент, когда достигнут узел у, узел все еще помечен как "новый". Все "новые" узлы, посещенные во время вызова процедуры станут потомками узла у в остовном лесу. Но не может закончиться, пока узел не достигнут, ибо находится в списке

Поиск в глубину задает на узлах остовного леса естественный порядок, а именно: узлы можно пометить в том порядке, в каком они посещались, если положить вначале между строками 6 и 7 алгоритма 5.2 и вставить в начало процедуры ПОИСК

Тогда узлы леса получат метки от 1 до их числа в лесу.

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

Пример 5.3. Поиск в глубину задает на графе, изображенном на рис. 5.7,а, следующий порядок: В этом можно убедиться, проследив порядок вызовов процедуры ПОИСК

на различных узлах, или пройдя дерево на рис. 5.7,б в прямом порядке.

Особо отметим, что если подлинный предок узла то Аналогично если у находится слева от в дереве, то