![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Глава 17. Свойства и типы графов. столбцу v, чтобы убедиться, что вершина не соединена ни с какой другой вершиной
Программа 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). Приведенные стоимости получены для простых реализаций, которые были описаны в предыдущих разделах; различные модификации, которые оказывают влияние на величину стоимостей, описываются в данном разделе.
|