Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 18. Поиск на графе. Независимо от структуры и представления графа, любой лес DFS позволяет нам определять, какие ребра являются древесными
|
|
18.5 Алгоритмы DFS
Независимо от структуры и представления графа, любой лес DFS позволяет нам определять, какие ребра являются древесными, а какие — обратными, и содействует правильному пониманию структуры графа, которое, в свою очередь, позволяет использовать поиск в глубину в качестве основы для решения многочисленных задач обработки графов. В разделе 17.7 мы уже ознакомились с основными примерами, имеющими отношение к поиску путей. В этом разделе мы рассмотрим реализации функции АТД, использующие DFS, позволяющие решать эту и многие другие типовые задачи. В остальной части данной главы и в нескольких последующих главах мы рассмотрим различные подходы к решению намного более сложных задач.
Обнаружение циклов. Существуют ли в заданном графе какие-либо циклы? (Является ли рассматриваемый граф лесом?) Эта задача легко решается с помощью поиска в глубину, поскольку любое обратное ребро дерева DFS принадлежит циклу, состоящему из этого ребра плюс путь в дереве, соединяющий два узла (см. рис. 18.9). Таким образом, можно немедленно воспользоваться поиском в глубину с целью выявления циклов: граф является ациклическим тогда и только тогда, когда во время выполнения поиска в глубину не встречаются обратные (или прямые!) ребра. Например, для проверки этого условия в программу 18.1 мы просто добавляем предложение else в оператор if с целью проверки равенства t и v. Если равенство установлено, это означает, что мы столкнулись с родительской связью w-v (второе представление ребра v-w, которое привело нас в w). Если равенство не установлено, то w-t завершает цикл в дереве DFS проверкой ребер из t в w. Более того, нет необходимости проверять все ребра: мы знаем, что должны найти цикл или завершить поиск, не обнаружив его, прежде чем проверим V ребер, поскольку любой граф с V или большим числом ребер должен содержать в себе цикл. Следовательно, мы можем проверить, является ли рассматриваемый граф ациклическим или за время, пропорциональное V в случае его представления в виде списков смежных вершин, хотя будет затрачено время, пропорциональное V1 (чтобы найти ребра), если граф задан в виде матрицы смежности.
Простой путь. Существует ли путь в графе, который связывает две заданных вершины? В разделе 17.7 мы видели, что нетрудно построить класс DFS, который способен решить эту задачу за линейное время.
Простая связность. Как следует из исследований, проведенных в разделе 18.3, мы за линейное время определяем, является ли граф связным, всякий раз, когда пользуемся поиском в глубину. В самом деле, выбранная нами стратегия основана на вызове функции поиска для каждой связной компоненты. При проведении поиска в глубину граф относится к категории связных тогда и только тогда, когда функция поиска на графе вызывает рекурсивную функцию DFS всего лишь один раз (программа 18.2). Число связных компонент в графе в точности равно числу вызовов рекурсивной функции из функции GRAPHsearch, следовательно, число связных компонент графа можно определить путем простого подсчета числа таких вызовов.
В общем случае программа 18.4 служит иллюстрацией класса DFS, который поддерживает выполнение запросов, касающихся связности, за постоянное время после этапа препроцессорной обработки в конструкторе. Он поддерживает тот же порядок посещения вершин, что и программа 18.3. Вместо ребра рекурсивная функция в качестве свое-
Часть 5. Алгоритмы на графах
го второго аргумента использует вершину, поскольку ей не нужно знать, кто является ее родителем. Каждому дереву леса DFS соответствует связная компонента графа, так что мы быстро можем определить, содержатся ли две вершины в одной и той же компоненте, включив в представление графа вектор, проиндексированный именами вершин, для последующего его заполнения через поиск в глубину и доступа со стороны запросов о связности. В рекурсивной функции DFS мы присваиваем текущее значение счетчика компоненты элементу вектора, соответствующему каждой посещенной вершине. Далее, мы знаем, что две вершины находятся в одной компоненте графа тогда и только тогда, когда соответствующие им элементы этого векторе равны. Опять-таки, обратите внимание на тот факт, что данный вектор отображает структурные свойства графа, но не особенности представления графа или динамики поиска.
Программа 18.4 типизирует базовый подход, который мы намереваемся использовать при решении различных задач обработки графов. Мы разработаем класс, ориентированный на решение специальных задач, чтобы клиенты могли создавать объекты, решающие эту задачу. Как правило, все время, затрачиваемое на предварительную обработку, расходуется конструктором, который вычисляет приватные данные, описывающие соответствующие структурные свойства графа. Эти свойства графа помогают обеспечить эффективную реализацию общедоступных функций запросов. В данном случае конструктор выполняет предварительную обработку с помощью поиска в глубину (за линейное время) и поддерживает приватные элементы данных (вектор id, проиндексированный именами вершин), который позволяет отвечать на запросы о связности за постоянное время. Что касается других задач обработки графов, то используемые нами конструкторы могут допускать более высокие затраты пространства памяти, времени на предварительную обработку и на ответы на запросы. Как обычно, основное внимание мы уделяем минимизации этих затрат, хотя во многих случаях сделать это весьма непросто. Например, большая часть главы 19 посвящена решению задачи связности орграфов, в рамках которых линейное время на предварительную обработку и постоянное время на обработку запросов о связности, аналогично программе 19.1, представляет собой труднодостижимую цель.
Программа 18.4. Связность графа____________________________________________
Конструктор СС вычисляет за линейное время количество связных компонент заданного графа и сохраняет индекс компоненты, ассоциированной с каждой вершиной, в приватном векторе id, проиндексированном именами вершин. Клиентские программы могут использовать объект СС для определения за постоянное время числа связных компонентов (count) или для проверки (connect), является ли связанной конкретная пара вершин.
template < class 6raph> class CC { const Graph & 6; int cent; vector < int> id; void ccR(int w) {
id[w] = cent;
typename Graph:: adjIterator A(G, w);
for (int v = A.beg();! A.end(); v = A.nxt())
if (id[v] == -1) ccR(v); >