Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 17. Свойства и типы графов. столбцу v, чтобы убедиться, что вершина не соединена ни с какой другой вершиной
|
|
столбцу v, чтобы убедиться, что вершина не соединена ни с какой другой вершиной. В то же время, в случае представления графа в виде векторов ребер у нас нет ничего лучшего, как только проверить все Е ребер, чтобы проверить, имеются ли какие-либо ребра, содержащие вершину v. Мы должны предоставить клиентским программам средства, которые позволят им избежать подобного рода вычислений, требующих больших затрат времени. Как уже отмечалось в разделе 17.2, один из способов достижения этой цели заключается в том, чтобы определить АТД клиента, для задачи, подобной рассмотренной в примере для программы 17.11. Такая реализация после выполнения предварительной обработки графа за время, пропорциональное размеру его представления, позволит клиентам определить степень любой вершины за постоянное время. Этот подход нельзя считать усовершенствованием, если клиент стремится определить степень только одной вершины, в то же время он обеспечивает существенную экономию ресурсов тем клиентам, которые хотят знать значения степеней некоторого множества вершин. Существенное различие в производительности алгоритма решения достаточно простой задачи в зависимости от условий его применения весьма характерно для обработки графов.
Программа 17.11. Реализация класса, определяющего степени вершин____________
Этот класс предлагает клиентским программам способ определения степени любой заданной вершины графа в классе GRAPH за.постоянное время после предварительной обработки в конструкторе, время которой линейно зависит от размеров графа (линейно зависимая обработка). Реализация основана на поддержке вектора степеней вершин, индексированного именами вершин, как элемента набора данных, и перегрузки [] как общедоступной функции-элемента. Мы инициализируем все элементы нулями, а затем выполняем обработку всех ребер графа, увеличивая на единицу значения соответствующих вхождений для каждого ребра.
Мы используем классы, подобные этому, на всем протяжении данной книги при создании объектно-ориентированных реализаций функций обработки графов как клиентов класса GRAPH.
template < class Graph> class DEGREE { const Graph & G;
vector < int> degree; public:
DEGREE(const Graph & G): G(G), degree(G.V(), 0) {
for (int v = 0; v < G.V(); v++) { typename Graph:: adjIterator A(G, v); for (int w = A.beg();! A. end(); w = A. nxt())
degree[v]++; } }
int operator [] (int v) const { return degree[v]; }
};
Для каждой задачи обработки графа из числа рассматриваемых в данной книге мы инкапсулируем ее решение в классах, подобных приведенному, с приватными элементами данных и общедоступными функциями-элементами, специфичными для каждой задачи. Клиенты создают объекты, функции-элементы которых реализуют обработку графов. Такой подход получает дальнейшее развитие в расширении интерфейса АДТ графа за
Часть 5. Алгоритмы на графах
счет определения множества взаимодействующих классов. Любое множество таких классов определяет интерфейс обработки графов, но каждый инкапсулирует собственные приватные данные и функции-элементы.
Существует много других способов разработки интерфейсов на C++. Одно из направлений дальнейших действий состоит в простом включении общедоступных функций-элементов (и любых других приватных элементов данных и функций-элементов, которые, возможно, потребуются) в определение базового АТД класса GRAPH. В то время как такой подход обладает всеми достоинствами, которыми мы восхищались в главе 4, ему свойственны также и серьезные недостатки, ибо такая сфера деятельности, как обработка графов, намного шире, чем виды базовых структур данных, которые служили объектом анализа в главе 4. Из всего множества этих недостатков в качестве основных выделим следующие:
■ Существует намного больше подлежащих реализации функций обработки графов,
чем те, которые мы можем должным образом определить в одном интерфейсе.
■ Простые задачи обработки графов должны пользоваться теми же интерфейсами,
которые необходимы для решения сложных задач.
■ Одна функция-элемент может получить доступ к элементам данных, предназначен
ных для использования другой функцией-элементом вопреки принципам инкапсу
ляции, которым мы намерены следовать.
Интерфейсы этого типа получили известность как насыщенные или " толстые1 (fat) интерфейсы. В книге, изобилующей алгоритмами обработки графов, подобного рода интерфейс и на самом деле становится " толстым".
Другой подход предусматривает использование механизма наследования для определения различных типов графов, который предоставляет клиентам различные наборы средств решения задач обработки графов. Сравнение этого замысловатого подхода с более простым подходом, который мы приняли к использованию, - это вполне достойное занятие при изучении проблем программного обеспечения, однако оно еще больше уводит нас от изучения алгоритмов обработки графов, нашей основной цели.
Таблица 17.1 показывает зависимость стоимости различных простых операций обработки графов от выбираемого представления графа. Эту таблицу следует внимательно изучить, прежде чем переходить к реализации более сложных операций; она поможет вам выработать четкое понимание трудности реализации различных простейших операций. Большинство значений стоимости вытекает непосредственна из анализа программных кодов, за исключением последней строки, которая будет подробно рассматриваться в конце данного раздела.
Таблица 17.1. Стоимости выполнения операций обработки графов
для худших случаев_______________________________________________________________
Рабочие характеристики основных операций АТД, осуществляющих обработку графов, существенно различаются в зависимости от выбора представления графа, даже если рассматривать только простейшие операции. Этот вывод следует из данных приводимой ниже таблицы стоимостей операций, составленной для худших случаев (эти различия не выходят за пределы постоянного множителя для больших значений V и E). Приведенные стоимости получены для простых реализаций, которые были описаны в предыдущих разделах; различные модификации, которые оказывают влияние на величину стоимостей, описываются в данном разделе.