Метод поиска в глубину
Метод поиска в глубину
Метод обхода узлов неориентированного графа называется поиском в глубину, так как процесс поиска идет в направлении вперед (вглубь) до тех пор, пока это возможно. Идея алгоритма состоит в следующем.
Выбираем и посещаем некоторый произвольный узел v. Затем выбираем произвольное ребро (v, w) и посещаем узел w. Пусть x – последний посещенный узел. Для продолжения процесса поиска выбираем какое-нибудь, не рассмотренное еще ребро (x, y). Если узел y уже посещался, ищем другое новое ребро, инцидентное x. Если y раньше не посещался, идем в y и заново начинаем поиск от узла y. Пройдя все пути, начинающиеся в y, возвращаемся в x, то есть в тот узел, из которого был впервые достигнут узел y. Затем продолжаем выбор нерассмотренных ребер, инцидентных узлу x, до тех пор, пока не будет исчерпан список этих ребер.
Этот метод поиска можно применить и на ориентированном графе. В этом случае, находясь в узле x, необходимо выбирать ребра (x, y), только выходящие из x. Исследовав все ребра, выходящие из y, возвращаемся в x даже тогда, когда в y входят другие ребра, еще не рассмотренные.
Метод поиска в глубину на неориентированном графе G = (V, E) разбивает множество его ребер E на два подмножества T и B. Ребро (v, w) помещается в T, если узел w не посещался до того момента, когда, рассматривая ребро (v, w), оказываемся в узле v. В противном случае, ребро (v, w) помещается во множество B.
Ребра из T называются древесными, а ребра из B – обратными. Подграф (V, T) представляет собой неориентированный лес, называемый остовным лесом для G, построенным поиском в глубину или глубинным остовным лесом для G.
Алгоритм поиска в глубину на неориентированном графе
Вход. Граф G = (V, E), представленный списками смежности узлов: L(v) "v Î V.
Выход. Разбиение множества E на два подмножества: древесных ребер T и обратных ребер B.
Рекомендуемые материалы
Метод. Рекурсивная процедура Поиск(v) добавляет к T ребро (v, w), если узел w был впервые достигнут во время прохождения по ребру из v. Все узлы вначале помечены как «новые».
1. T = Æ.
2. Выбираем произвольный узел v Î V. Помечаем его как “новый”.
3. Пока существует v Î V, помеченный как “новый”, выполняем процедуру Поиск(v).
Процедура Поиск(v):
4. Пометить узел v как «старый».
5. Для любого узла w Î L(v) делать:
6. Если узел w – «новый», то
7. Добавить ребро (v, w) к T
8. Поиск(w)
Все ребра множества E, не попавшие в T, относятся к множеству B.
Пример работы алгоритма поиска в глубину на неориентированном графе представлен на рис. 17.
Обычно ребра, входящие в T, изображают сплошными линиями, а ребра из B – пунктирными. Корень (то есть вершину, выбранную за начало поиска) рисуют сверху, а сыновей располагают слева направо в порядке их прохождения (рис. 17).
Рис. 17. Неориентированный граф (а) и глубинный остовный лес для него (б)
Поиск в глубину в ориентированном графе
Рассмотренный алгоритм поиска можно использовать, чтобы находить ориентированный остовный лес для ориентированного графа G = (V, E), если определить список L(v) узлов, «смежных» с узлом v как список узлов, которые являются концами ребер с началом в узле v. То есть, L(v) = {w: (v, w) Î E}. Пример представлен на рис. 18.
В процессе поиска в глубину на ориентированном графе в дополнение к древесным ребрам возникает еще три типа ребер. Это обратные ребра (например, (v3, v1)), поперечные справа налево (например, (v4, v3)) и прямые ребра (например, (v1, v4)).
Но никакое ребро не идет из узла с меньшим номером, присвоенным в процессе поиска в глубину, в узел с большим номером, если только последнее не является потомком первого. Это не случайно.
Пусть (v, w) – ребро, и узел v был впервые посещен до w (то есть v < w). Каждый узел, которому присваивается номер в период между началом и концом процедуры Поиск(v), становятся потомком узла v. Но узел w должен получить свой номер, когда рассматривается ребро (v, w), если только он уже не получил номер раньше. Если w получает номер, когда рассматривается ребро (v, w), то (v, w) становится древесным ребром, иначе – прямым. Таким образом, не может быть такого поперечного ребра (v, w), что v < w.
Лекция "9.2 Конфликт личность группа" также может быть Вам полезна.
Рис. 18. Ориентированный граф (а) и ориентированный глубинный остовный лес для него (б)
Поиск в глубину в ориентированном графе G = (V, E) разбивает множество его ребер на 4 класса:
1. Древесные ребра, идущие к новым узлам в процессе поиска.
2. Прямые ребра, идущие от предков к подлинным потомкам, но не являющиеся древесными ребрами.
3. Обратные ребра, идущие от потомков к предкам (возможно из узла в себя).
4. Поперечные ребра, соединяющие узлы, которые не являются ни предками, ни потомками друг друга.
