Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
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 проявляет намного большее быстродействие, чем указанные выше методы. Задача поиска оптимального алгоритма (такого, чтобы гарантировал решение задачи за время, пропорциональное V2) вычисления транзитивного замыкания насыщенного DAG все еще не решена. Широко известная граница производительности для худшего случая достигает уровня VE. В то же время нас больше устраивает алгоритм, который выполняется быстрее на некотором обширном классе графов DAG, такой как, например, алгоритм, реализованный программой 19.9, чем алгоритм, который, подобно программе Часть 5. Алгоритмы на графах 19.4, в любом случае выполняется за время, пропорциональное VE. В разделе 19.9 мы убедимся, что подобного рода увеличение производительности для графов DAG оказывает также непосредственное влияние на нашу способность вычислять транзитивные замыкания орграфов общего вида.
|