Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Bool searchR (int v, int w)
|
|
{
if (v == w) return true; visited[v] = true;
typename Graph:: adjIterator A(G, v); for (int t = A.beg();! A.end(); t = A.nxt()) if (! visited[t])
if (searchR(t, w)) return true; return false; } public:
sPATH (const Graph & G, int v, int w): G(G), visited(G.V(), false) { found e searchR(v, w); } bool exists () const { return found; }
};
Программа 17.16 просто проверяет, существует тот или иной путь. Как следует расширить ее с тем, чтобы она могла печатать ребра, составляющие путь? Рекурсивный подход предлагает простое решение:
■ Добавить оператор печати ребра v-t сразу же после того, как рекурсивный вызов
в функции searchR находит путь из t в w.
■ В вызове функции searchR из конструктора поменять местами v и w.
Первое изменение приводит к тому, что путь из v в w печатается в обратном порядке: если в результате вызов searchR(t, w) находит путь из t в w (и печатает ребра, составляющие этот путь, в обратном порядке), то печать пути t-v завершает решение задачи поиска пути из v в w. Второе изменение меняет порядок: чтобы распечатать ребра, составляющие путь из v в w, мы распечатываем путь из w в v в обратном порядке. (Этот прием работает только в случае неориентированных графов.) Мы могли бы применить эту стратегию для реализации функции АТД, которая вызывает функцию, переданную клиентом, для каждого ребра, составляющего путь (см. упражнение 17.88).
Рисунок 17.17 представляет собой пример динамики рекурсии. Как и в случае любой другой рекурсивной программы (в принципе, любой программы с вызовами функций), такую трассировку нетрудно вывести на печать: чтобы внести соответствующие изменения в программу 17.16, мы можем добавить переменную depth, значение которой увеличивается на 1 при входе и уменьшается на 1 при выходе, чтобы отслеживать глубину ре-
Глава 1 7. Свойства и типы графов
курсии, затем поместить в начало рекурсивной функции программный код, осуществляющий depth пропусков при печати, за которыми следует соответствующая информация (см. упражнения 17.86 и 17.87).
Свойство 17.2. Мы можем найти путь, соединяющий две заданных вершины графа, за линейное время.
Рекурсивная функция поиска в глубину, реализованная в программе 17.16, представляет собой доказательство методом индукции того факта, что функция АТД определяет, существует искомый путь или нет. Такое доказательство легко можно расширить с целью установки, что в худшем случае программа 17.16 проверяет все элементы матрицы смежности в точности один раз. Аналогично, мы можем показать, что подобного рода программы, ориентированные на списки смежных вершин, проверяют в худшем случае все ребра графа в точности два раза (по разу в каждом направлении). ■
Мы используем термин линейный (linear) в контексте алгоритмов на графах, подразумевая под этим, что некоторое количественное значение не превосходит величины V+ Е (т.е. размеры графа), умноженной на соответствующий постоянный коэффициент. Как мы отметили в конце раздела 17.5, такое значение обычно не превосходит размера представления графа, умноженного на соответствующий постоянный коэффициент. Свойство 17.2 сформулировано таким образом, что оно позволяет использовать представление разреженных графов в виде списков смежных вершин и представление насыщенных графов в виде матрицы смежности, что, собственно говоря, и является нашей обычной практикой. Термин " линейный" не принято применять для описания алгоритма, который использует матрицу смежности и выполняется за время, пропорциональное V1 (даже если он линеен по отношению к размерам представления графа), если рассматриваемый граф не принадлежит к числу насыщенных. В самом деле, если мы используем представление графа в виде матрицы смежности, мы не можем подобрать алгоритм, линейный в смысле времени исполнения, для любой задачи обработки графа, которая требует анализа каждого ребра.
