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

Методы обхода графа.

Под обходом графа понимается перебор его вершин в определенном порядке, связанный с проходом по некоторым ребрам.

Существует много алгоритмов на графах, в основе которых лежит системати­ческий перебор вершин графа, такой, что каждая вершина просматривается в точности один раз. Поэтому такой задачей является нахождение хороших ме­тодов поиска в графе. Вообще говоря, метод поиска «хорош», если

• (а) он позволяет алгоритму решения интересующее нас задачи легко «по­грузиться» в этот метод и

• (б) каждое ребро графа анализируется не более одного раза (или, что существенно не меняет ситуации, число раз, ограниченное константой).

Опишем теперь такой метод поиска и неориентированном графе, который стал одной из основных методик проектировании графовых алгоритмов. Этот метод называется поиском в глубину.

06щая идея этого метода состоит в следующем. Мы начинаем поиск с неко­торой фиксированной вершины v₀,. затем выбираем произвольную вершину u, смежную с v₀, и повторяем наш процесс от u, В общем случае предположим, что мы находимся в вершине u. Если существует новая (еще не просмотренная) вершина u, u — v, то мы рассматриваем эту вершину (она перестает быть новой), и, начиная с нее, продолжаем поиск. Если же не существует ни одной новой вер­шины, смежной с v, то мы говорим, что вершина v использована, возвращаемся в вершину, из которой мы попали в v, и продолжаем процесс (если v= v₀, то поиск закончен). Другими словами, поиск в глубину из вершины v основывает­ся на поиске в глубину из всех новых вершин, смежных с v.

Пример. Пусть дан граф G=(V, Е).

Получаем следующую последовательность вершин поиска в глубину: 1-2-4-6-8-9-7-10-5-3.

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

Дата добавления: 2014-01-20