T.insert(Edge(w, t));

if (pre[t] > pre[w]) continue;

if (pre[t] == -1) tcR(t);

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

if (T.edge(t, i)) T.insert(Edge(w, i)); } } public:

dagTC(const Dag & D): D(D), cnt(0), pre(D.V(), -1), T(D.V(), true) { for (int v = 0; v < D.V(); v++)

if (pre[v] == -1) tcR(v); } bool reachable (int v, int w) const { return T.edge(v, w); }

};

Если рассматриваемый DAG не имеет прямых ребер (см. упражнение 19.42), время выполнения программы 19.9 пропорционально VX, и в этом аспекте она никак не пре­восходит алгоритмы транзитивного замыкания, которые мы анализировали применитель­но к орграфам общего вида в разделе 19.3 (как, например, программа 19.4), равно как и подход, основанный на применении топологической сортировки, описание которой изложено в начале данного раздела. С другой стороны, если число прямых вершин ве­лико (или, что одно и то же, число поперечных ребер мало), то программа 19.9 прояв­ляет намного большее быстродействие, чем указанные выше методы.

Задача поиска оптимального алгоритма (такого, чтобы гарантировал решение задачи за время, пропорциональное V²) вычисления транзитивного замыкания насыщенного DAG все еще не решена. Широко известная граница производительности для худшего случая достигает уровня VE. В то же время нас больше устраивает алгоритм, который выполняется быстрее на некотором обширном классе графов DAG, такой как, например, алгоритм, реализованный программой 19.9, чем алгоритм, который, подобно программе

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