Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
АТД графа
|
|
Мы разрабатываем наши алгоритмы обработки графов, используя для этой цели абстрактный тип данных (АТД), который позволяет сформулировать фундаментальные задачи, используя стандартный механизм, введенный в главе 4. Программа 17.1 представляет собой интерфейс АТД, который будет использоваться для этих целей. Базовые представления и реализации графа для этого АТД рассматриваются в главах 17.3-17.5. Далее в этой книге, всякий раз, когда мы будем рассматривать новые задачи обработки графов, мы будем также проводить исследования алгоритмов их решения и реализации этих алгоритмов в контексте клиентских программ и абстрактных типов данных, которые получают доступ к графам через этот интерфейс. Такая схема позволит решать задачи обработки графов в диапазоне от элементарных функций поддержки до сложных решений трудных проблем.
В основу рассматриваемого интерфейса положен применяемый нами стандартный механизм, который скрывает представления и реализации от клиентских программ (см. раздел 4.8). Он также включает определение простой структуры, которая позволяет нашим программам манипулировать ребрами некоторым единообразным способом. Такой интерфейс предоставляет в распоряжение клиентов базовый механизм, который позволяет им строить графы (сначала строится граф, затем к нему добавляются ребра), осуществлять поддержку графов (путем удаления некоторых ребер и добавления новых) и исследовать графы (путем использования итератора для обработки вершин, смежных по отношению к заданной вершине).
Часть 5. Алгоритмы на графах
Программа 17.1. Интерфейс АТД графа
Этот интерфейс представляет собой отправную точку для реализации и тестирования алгоритмов обработки данных. Он определяет два типа данных: тривиальный тип данных Edge, включающий функцию конструктора, которая строит ребро по двум заданным вершинам, и тип данных GRAPH, определение которого дается в соответствии с методологией стандартного, независимого от представления интерфейса АТД, описанного в главе 4.
Конструктор GRAPH принимает два аргумента: целое, задающее число вершин, и булевское значение, которое показывает, является ли граф ориентированным или неориентированным (орграф), при этом неориентированный граф подразумевается по умолчанию.
Базовые операции, которые мы используем для обработки графов и орграфов, суть функции АТД, обеспечивающие их построение и уничтожение, функции для подсчета числа вершин и ребер, а также для добавления и удаления ребер. Класс итератора adjlterator позволяет клиентам проводить обработку любых вершин, смежных по отношению к заданной вершине. Программы 17.2 и 17.3 служат иллюстрацией его использования.
struct Edge { int v, w;
Edge(int v = -1, int w = -1): v(v), w(w) { } };
class GRAPH { private:
// Код, зависящий от реализации public:
GRAPH(int, bool); -GRAPH (); int V() const; int E() const; bool directed() const; int insert(Edge); int remove(Edge); bool edge (int, int); class adjlterator { public:
adjlterator (const GRAPH &, int); int beg(); int nxt(); bool end(); }; >;
АТД в программе 17.1 представляет собой основной механизм, который позволяет нам разрабатывать и осуществлять тестирование алгоритмов; это отнюдь не универсальный интерфейс. Как обычно, мы работаем с простейшим интерфейсом, который поддерживает базовые операции обработки графов, исследование которых мы намерены провести. Определение такого интерфейса для использования в практических приложениях требует достижения многочисленных компромиссов между простотой, эффективностью и универсальностью. Далее мы рассмотрим лишь некоторые из таких компромиссов; остальные мы будем анализировать в контексте реализаций и приложений, которые будут встречаться на протяжении всей этой книги.