Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Class adjIterator
|
|
{
public:
adjlterator(const GRAPH &, int); Edge *beg(); Edge *nxt(); bool end();
}; };
Более приемлемая для клиентов альтернатива предусматривает объявление типа данных Edge и, в условиях нашей реализации, манипулирование указателями на ребра. В программе 20.1 содержатся подробности использования интерфейсов EDGE, GRAPH и итератора АТД, который применяется для поддержки этого подхода. Для использования в других контекстах клиенты легко могут выполнить минимальные требования типа данных Edge, сохраняя при этом гибкость, позволяющую давать определения типов данных, отражающих специфику конкретных приложений. Предлагаемые нами реализации могут манипулировать указателями на ребра и использовать интерфейс с целью извлечения не-
Часть 5. Алгоритмы на графах
обходимой им информации из интерфейсов EDGE независимо от их представления. Программа 20.2 представляет собой пример клиентской программы, которая использует этот интерфейс.
Программа 20.2. Пример клиентской функции обработки графа_______________________
Данная функция служит иллюстрацией использования интерфейса взвешенного графа, предложенного нами в программе 20.1. При любой реализации этого интерфейса функция edges возвращает вектор, содержащий указатели на все ребра графа. Как и в главах 17-19, мы в общем случае используем функцию итератора только так, как показано здесь.
template < class Graph, class Edge> vector < Edge *> edges(const Graph & G) { int E = 0;
vector < Edge *> a (G.E ());
for (int v = 0; v < G.V(); v++)
{
typename Graph:: adjIterator A(G, v);
for (Edge* e = A.beg();! A.end(); e = A.nxt())
if (e-> from(v)) a[E++] = e; }
return a; }
Программа 20.3. Класс взвешенного графа
(представление в виде матрицы смежности)___________________________________
Для насыщенных взвешенных графов мы используем матрицу указателей на данные типа Edge с указателем на ребро в v-u в строке v и столбце w. Для неориентированных графов мы устанавливаем другой указатель на ребро в строке w и столбце v. Нулевой указатель свидетельствует об отсутствии соответствующего ребра; когда мы удаляем ребро с помощью функции remove(), мы удаляем указатель на него. Рассматриваемая реализация не производит проверки на наличие параллельных ребер, в то же время клиенты могут для этой цели воспользоваться функцией edge.
template < class Edge> class DenseGRAPH { int Vcnt, Ecnt; bool digraph; vector < vector < Edge *> > ad j; public:
DenseGRAPH(int V, bool digraph = false): adj(V), Vcnt(V), Ecnt(O), digraph(digraph) { for (int i = 0; i < V; i++)
adj[i].assign(V, 0); }
int V() const { return Vcnt; } int E() const { return Ecnt; } bool directed() const { return digraph; } void insert(Edge *e)
{ int v = e-> v(), w = e-> w(); if (adj[v][w] == 0) Ecnt++; adj[v][w] =е;
if (! digraph) adj [w] [v] = e; }
void remove(Edge *e) { int v = e-> v(), w =e-> w(); if (adj[v][w]! = 0) Ecnt--; adj[v][w] - 0;
Глава 20. Минимальные остовные деревья
if (! digraph) adj[w][v] = 0; } Edge* edge (int v, int w) const
{ return adj[v][w]; } class adjIterator; friend class adjlterator; };
В алгоритмах тестирования и в базовых приложениях мы используем класс EDGE (ребро), имеющий два приватных элемента данных типа int и double, которые инициализируются аргументами конструктора и являются возвращаемыми значениями, соответственно, функций-элементов v(), w() и wt() (см. упражнение 20.8). Во избежание распространения простых типов данных, на протяжении данной главы и главы 21 мы будем использовать для представления веса ребер тип данных double. В наших примерах в качестве весов ребер мы будем использовать вещественные числа из диапазона от 0 до 1. Это решение не противоречит различным альтернативам, которые могут понадобиться в приложениях, поскольку мы можем явно или неявно изменить веса таким образом, чтобы они соответствовали этой модели (см. упражнения 20.1 и 20.10.). Например, если весами являются целые числа, меньшие некоторого известного максимального значения, то поделив значения весов на это максимальное значение, мы преобразуем их в вещественные числа, принимающие значения в диапазоне от 0 до 1.