Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Простые, эйлеровы и гамильтоновы пути
|
|
Первый рассмотренный нами нетривиальный алгоритм обработки графов решает фундаментальные задачи, касающиеся поиска путей в графах. Для решения этих задач мы вводим принцип общей рекурсии, который будем широко применять на протяжении всей книги, они служат иллюстрацией того, что на первый взгляд очень похожие задачи существенно различаются по трудности их решения.
Эти задачи уводят нас от локальных свойств, таких как существование конкретных ребер или определение степеней вершин, к глобальным свойствам, которые могут многое сказать о структуре графа. Фундаментальное свойство графа говорит нам, связаны ли какие-либо две вершины графа или нет. Если они связаны, то возникает следующий вопрос, который нас интересует: как найти простейший путь, который их связывает.
Простой путь. Если заданы две какие-либо вершины графа, существует ли путь, который их соединяет? В условиях некоторых приложений нам вполне достаточно знать, существует или не существует такой путь, но данном случае наша задача заключается в том, чтобы найти конкретный путь.
Программа 17.16 предлагает решение этой задачи. В ее основу положен поиск в глубину {depth-first search) — фундаментальный принцип обработки графов, на котором мы кратко останавливались в главах 3 и 5 и который подробно будем изучать в граве 18. Этот алгоритм построен на базе приватной функции-элемента, которая определяет, существует ли простой путь из вершины v в вершину w путем проверки для каждого ребра v-t инцидентного v, существует ли простой путь из t в w, который не проходит через v. Он использует вектор, индексированный именами вершин, с целью пометить v, чтобы ни при каком рекурсивном вызове путь, проходящий через v, не проверялся.
Часть 5. Алгоритмы на графах
Программа 17.16. Поиск простого пути
Этот класс использует рекурсивную функцию поиска в глубину searchR, чтобы найти простой путь, соединяющий две заданных вершины графа, и предоставляет клиенту функцию-элемент exist, чтобы клиентская программа могла проверить, существует ли путь между этими вершинами. В случае, когда заданы две вершины v и w, функция searchR проверяет каждое ребро v-t, смежное с v, может ли оно быть первым ребром на пути к w. Вектор visited, индексированный именами вершин, предотвращает повторный заход на любую вершину, так что обеспечивается прохождение только простых путей.
template < class Graph> class sPATH { const Graph & G;
vector < bool> visited;
|
|