Class DenseGRAPH

{ int Vent, Ecnt; bool digraph;

vector < vector < bool> > adj; public:

DenseGRAPH(int V, bool digraph = false) adj(V), Vent(V), Ecnt(0), digraph(digraph)

{

for (int i = 0; i < V; i++)

adj[i].assign(V, false); }

int V() const { return Vent; } 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] == false) Ecnt++;

adj [v] [w] a= true;

if (! digraph) adj [w] [v] = true;

} void remove (Edge e)

{ int v = e.v, w = e.w;

if (adj[v][w] == true) Ecnt--; adj[v][w] = false; if (! digraph) adj[w][v] = false; } bool edge (int v, int w) const

{ return adj[v][w]; } class adjIterator; friend class adjIterator; };

Чтобы добавить в граф ребро, мы присваиваем элементам указанной матрицы значе­ние false (одно для орграфов, два для неориентированных графов). Такое представление не допускает параллельных ребер: если в граф нужно вставить ребро, для которого со­ответствующие вхождения матрицы уже получили значение 1, то программа не дает ре­зультата. В некоторых проектах АТД может оказаться целесообразным информировать клиента о попытке включить параллельное ребро, возможно, код возврата операции insert. Это представление допускает использование петель: ребро v-v представляется не­нулевым значением элемента a[v][v].

Программа 17.8. Итератор для представления матрицы смежности_______________

Данная реализация итератора для программы 17.7 использует индекс /для просмотра значений строки v матрицы смежности (adj[v]), пропуская элементы, имеющие значение false. Вызов функции beg(), за которым следует последовательность вызовов функций nxt() (проверка того, что значением функции end() является false перед каждым таким вызовом), позволяет получить последовательность вершин, смежных с вершиной v графа G в порядке возрастания индексов вершин.

class DenseGRAPH:: adjIterator { const DenseGRAPH & G; int i, v;