Глава 18. Поиск на графе. вершиной назначения ребра, помещенного в бахрому, тогда и только тогда, когда она помечена (значение ord[v] не равно -1).

вершиной назначения ребра, помещенного в бахрому, тогда и только тогда, когда она помечена (значение ord[v] не равно -1).

#include " GQ.cc"

template < class Graph>

class PFS: public SEARCH< Graph>

{ vector< int> st;

void searchC(Edge e) { GQ< Edge> Q(G.V());

Q.put(e); ord[e.w] = cnt++; while (! Q.empty ()) {

e = Q.get(); st[e.w] = e.v; typename Graph:: adjIterator A(G, e.w); for (int t = A.beg();! A.end(); t = A.nxt()) if (ord[t] == -1)

{ Q.put(Edge(e.w, t)); ord[t] = cnt++; } else

if (st[t] == -1) Q.update (Edge (e.w, t)); } } public:

PFS(Graph & G): SEARCH< Graph> (G), st(G.V(), -1)

{ search(); }

int ST(int v) const { return st[v]; } };

Свойство 18.12. Обобщенный просмотр графа посещает все вершины и ребра графа за время, пропорциональное V¹ в случае представления графа в виде матрицы смежности, и пропорциональное V + Е в случае представления графа в виде списков смежных вершин плюс, в худшем случае, время, затрачиваемое на V операций вставки, V операций удаления и Е операций обновления в очереди размера V.

Доказательство: Доказательство свойства 18.12 не зависит от реализации очереди и благодаря этому обстоятельству следует из полученных ранее результатов. Указанные в формулировке свойства дополнительные затраты времени на операции, выполняе­мые обобщенной очередью, следуют непосредственно из программной реализации. ■

Существует множество других, заслуживающих внимания, эффективных моделей АТД бахромы. Например, как и в случае первой предложенной нами реализации поиска в ширину, мы можем воспользоваться нашей первой обобщенной схемой и просто поме­стить все ребра в бахрому и игнорировать те их них, которые ведут в вершины, уже вклю­ченные в дерево в тот момент, когда мы извлекаем их из бахромы. Недостаток такого подхода, как и в случае поиска в ширину, заключается в том, что максимальный размер очереди должен быть равным E а не V. Либо мы должны выполнять обновления неявно в рамках реализации АТД, следя за тем, чтобы никакие два ребра с одной и той же вер­шиной назначения не могли одновременно находиться в очереди. Однако простейший способ реализации АТД, решающего эту задачу, по существу, эквивалентен использова­нию вектора, индексированного именами вершин (см. упражнения 4.51 и 4.54), ибо про­верка этого вектора более удобна для клиентских программ, применяющих поиск на графе.