Часть 5, Алгоритмы на графах

class SparseMultiGRAPH { int Vent, Ecnt; bool digraph; struct node { int v; node* next;

node (int x, node* t) { v = x; next = t;)

};

typedef node* link; vector < link> adj; public:

SparseMultiGRAPH(int V, bool digraph = false) adj(V), Vcnt(V), Ecnt(O), digraph(digraph) { adj.assign(V, 0); } 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;

adj [v] = new node(w, adj [v]); if (! digraph) adj[w] = new node(v, adj[w]) Ecnt++; }

void remove(Edge e); bool edge (int v, int w) const; class adjIterator; friend class adjIterator; };

Программа 17.10. Итератор для представления графа в виде списка смежных вершин

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

class SparseMultiGRAPH:: adjIterator { const SparseMultiGRAPH & G; int v; link t; public:

adjlterator(const SparseMultiGRAPH & G, int v):

G(G), v(v) { t = 0; } int beg()

{ t = G.adj[v]; return t? t-> v: -1; } int nxt()

{ if (t) t = t-> next; return t? t-> v: -1; } bool end()

{ return t == 0; } };

В отличие от программы 17.7 программа 17.9 строит мультиграфы благодаря тому, что она не удаляет параллельных ребер. Выявление дубликатов ребер в структуре списка смежных вершин делает необходимым просмотр списков и может потребовать затрат вре­мени, пропорциональных V. Аналогично, в программе 17.9 отсутствует реализация опе­рации удалить ребро (remove edge) или проверка наличия ребра. Включение реализаций этих