Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 17. Свойства и типы графов. В общем случае задачи обработки графов, которые исследуются в этой книге, подразделяются на три обширных категории:
|
|
В общем случае задачи обработки графов, которые исследуются в этой книге, подразделяются на три обширных категории:
■ Вычисления значений некоторых размеров графа.
■ Выбор некоторого подмножества ребер графа.
■ Ответы на вопросы, касающиеся некоторых свойств графа.
Примеры, относящиеся к первой категории, суть количество связных компонент и длина кратчайшего пути между двумя заданными вершинами графа; примеры, относящиеся ко второй категории, связаны с остовным деревом и циклом наибольшей длины, который содержит заданную вершину; примеры третьей категории составляют вопросы наподобие: находятся ли заданные вершины в одной и той же компоненте. В самом деле, условия, которые мы определили в разделе 17.1, немедленно выводят нас на множество вычислительных задач.
Программа 17.4. Интерфейс ввода/вывода для функций обработки графов______________
Этот класс служит иллюстрацией способа упаковки родственных функций в единый класс. Он определяет функции, выполняющие печать графа (см. программу 17.3), вставку ребер, вводимых в виде пар целых чисел через стандартный ввод (см. упражнение 17.12) и вставку ребер, вводимых в виде пар символов через стандартный ввод (см. программу 17.14).
template < class Graph> class I0 { public:
static void show(const Graph &); static void scanEZ(Graph &); static void scan(Graph &); };
Наш подход к решению такого рода задач предполагает построение абстрактных типов данных (АТД), которые являются клиентами базовых АТД из программы 17.1, однако это, в свою очередь, позволяет определить клиентские программы, требуемые для решения реальных задач. Например, программа 17.5 есть интерфейс для АТД связности графа. Мы можем написать клиентские программы, использующие этот АТД для построения объектов, которые вычисляют количество связных компонентов в графе и которые могут проверить, находятся ли любые две вершины в одной и той же связной компоненте. Описание реализаций этого АТД и их рабочие характеристики мы даем в разделе 18.5; мы разрабатываем АТД подобного рода на протяжении всей книги. Обычно такие АТД содержат общедоступную функцию-элемент, выполняющую предварительную обработку (preprocessing) (обычно это конструктор), приватные элементы данных, которые содержат информацию, полученную во время предварительной обработки, и общедоступные функции-элементы обслуживания запроса (query), которые используют эту информацию для предоставления клиентам информации о графе.
В этой книге мы работаем главным образом со статическими {static) графами, которые содержат фиксированное число вершин V ребер Е. В общем случае мы выполняем построение графов, осуществляя Е вызовов функции insert с последующим их обработкой либо в результате вызова соответствующей функции АТД, которая принимает граф
Часть 5. Алгоритмы на графах
в качестве аргумента и возвращает некоторую информацию, касающуюся графа, либо за счет использования объектов указанного выше вида, которые служат для предварительной обработки графа с целью обеспечить возможность эффективного ответа на запросы, касающиеся графа. В любом случае, изменения графа путем обращения к функциям insert и remove обусловливает необходимость повторной обработки графа. Динамические задачи, в рамках которых мы хотим совместить обработку графов с добавлением или удалением вершин и ребер графа, приводят нас в область интерактивных алгоритмов (on-line algorithm), известных также как динамические алгоритмы (dynamic algorithms), в которой приходится сталкиваться с другими сложными проблемами. Например, проблема связности, которую мы решали с помощью алгоритма объединения-поиска в главе 1, представляет собой пример интерактивного алгоритма, поскольку мы можем получить информацию о связности графа во время включения ребер в этот граф. АТД из программы 17.1 поддерживает операции вставить ребро (insert edge) и удалить ребро (remove edge), благодаря чему клиенты могут использовать их для внесения изменений в графы, однако выполнение некоторых последовательностей операций сопряжено со снижением производительности. Например, алгоритмы объединения-поиска могут потребовать повторной обработки всего графа, если клиент использует операцию удалить ребро. Большая часть проблем, связанных с обработкой графов, с которыми мы сталкиваемся при добавлении или удалении нескольких ребер, может кардинально изменить природу графа, чем и объясняется необходимость его повторной обработки.
Программа 17.5. Интерфейс связности_______________________________________
Данный интерфейс АТД служит иллюстрацией типичной парадигмы, которую мы используем для реализации алгоритмов обработки графов. Он предоставляет клиенту возможность строить объекты, которые выполняют обработку графа таким образом, чтобы отвечать на запросы, касающиеся связности этого графа. Функция-элемент count возвращает число связных компонент графа, а функция-элемент connect проверяет, имеется ли связь между двумя заданными вершинами. Программа 18.4 представляет собой реализацию этого интерфейса.
template < class Graph> class CC { private:
// Код, зависящий от реализации public:
CC(const Graph &); int count(); bool connect(int, int); };
Одна из наиболее важных и сложных проблем, которая встает перед нами при обработке графа, заключается в том, чтобы получить четкое понимание рабочих характеристик реализаций и убедиться в том, что клиентские программы правильно ими пользуются. Как и в случае более простых задач, которые рассматривались в частях 1-4, выбранная методика использования абстрактных типов данных позволяет решать эти проблемы в логической последовательности.