Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Программа 20.4. Класс итератора, ориентированный на представление графа
|
|
в виде матрицы смежности_________________________________________________
Данный программный код, возвращающий указатели на ребра, является простой адаптацией программы 17.8.
template < class Edge>
class DenseGRAPH< Edge>:: adjIterator
{ const DenseGRAPH< Edge> & G;
int i, v; public:
adjIterator(const DenseGRAPH< Edge> & G, int v):
G(G), v(v), i(0) { } Edge *beg()
{ i = -1; return nxt(); } Edge *nxt() { for (i++; i < G.V(); i++)
if (G.edge(v, i)) return G.adj[v][i]; return 0; } bool end() const
{ return i > = G.V(); } };
При желании можно было бы разработать интерфейс АТД более общего характера, и использовать для весов ребер любой тип данных, который поддерживает операции сложения, вычитания и сравнения, поскольку мы совершаем более сложные манипуляции с весами, чем просто накопление их сумм и принятие решений в зависимости от значений этих сумм. В алгоритмах, построенных в главе 22, мы выполняем сравнения линейных комбинаций весов ребер, а время выполнения некоторых алгоритмов зависит от ариф-
Часть 5. Алгоритмы на графах
метических свойств весов, вследствие чего мы переходим к использованию целочисленных весов, тем самым упрощая анализ алгоритмов.
Программы 20.2 и 20.3 реализуют абстрактный тип данных взвешенного графа, представленного в виде матрицы смежности, который впервые был использован в программе 20.1. Как и ранее, вставка ребра в неориентированный граф сопряжена с хранением указателей на него в двух местах матрицы — по одному для каждой ориентации ребра. Как это характерно для алгоритмов, предполагающих применение представлений неориентированных графов в виде матриц смежности, их время выполнения пропорционально V1 (на инициализацию матрицы) и выше.
Имея такое представление, мы проводим тест на существование ребра v-w путем проверки, принимает ли указатель, расположенный на пересечении строки v и столбца w, нулевое значение. В некоторых ситуациях мы можем избежать проверок подобного рода, воспользовавшись сигнальными значениями для весов, однако в своих реализациях мы не будем использовать сигнальные значения.
Программа 20.5. Класс взвешенного графа (списки смежных вершин)___________________
Данная реализация интерфейса из программы 20.1 основана на представлении графа в виде списков смежных вершин и поэтому хорошо подходит для разреженных взвешенных графов. Как и в случае невзвешенных графов, мы представляем каждое ребро узлом списка, но в рассматриваемом случае каждый узел содержит указатель на ребро, которое он представляет, а не только на вершину назначения. Класс итератора представляет собой непосредственную адаптацию программы 17.10 (см. упражнение 20.13).
template < class Edge> class SparseMultiGRAPH { int Vcnt, Ecnt; bool digraph; struct node
{ Edge* e; node* next;
node(Edge* e, node* next): e(e), next(next) {} };
typedef node* link; vector < link> adj; public:
SparseMultiGRAPH(int V, bool digraph = false): adj(V), Vcnt(V), Ecnt(O), digraph(digraph) { } int V() const { return Vcnt; } int E() const { return Ecnt; } bool directed() const { return digraph; } void insert(Edge *e) {
adj[e-> v()] = new node(e, adj[e-> v()}); if (! digraph)
adj[e-> w()] = new node(e, adj[e-> w()]); Ecnt++; }
class adjIterator; friend class adjIterator; };
В программе 20.5 содержатся подробности реализации АТД взвешенного графа, который использует указатели на ребра в представлении графа в виде матрицы смежности. Вектор, проиндексированный именами вершин, ставит в соответствие каждой вершине связный список инцидентных ей ребер. Каждый узел списка содержит указатель на не-