Эффективный алгоритм поиска транзитивного замыкания ориентированного ациклического графа

Я пытаюсь решить проблему с графиком (это не для домашней работы, просто для тренировки моих навыков). Дана DAG , где V - множество вершин, а E - ребра. Граф представлен в виде списка смежности, поэтому A v - это множество, содержащее все соединения v . Моя задача состоит в том, чтобы найти , какие вершины достижимы из каждой вершины об ∈ V . Решение, которое я использую, имеет сложность O ( V 3$G(V,E)$$V$$E$$A_v$$v$$v\in V$$O(V^3)$, с транзитивным замыканием, но я читал, что в блоге это может быть быстрее, хотя он не показал, как. Может кто-нибудь сказать мне другой способ (с большей сложностью), чтобы решить проблему транзитивного замыкания в DAG?

Тот факт, что наш граф является ациклическим, значительно упрощает эту проблему.

Топологическая сортировка может дать нам порядок вершин такой, что если i < j , то не существует ребра от v j до v i . Мы перечислили вершины так, что все ребра в нашем списке идут вперед.$v_1,v_2,\dots,v_n$$i < j$$v_j$$v_i$

(отредактировано, чтобы исправить анализ и дать немного более быстрый алгоритм)

Теперь мы просто вернемся назад по этому списку, начиная с последней вершины . Транзитивное замыкание v n само по себе. Также добавьте v n к транзитивному замыканию каждой вершины с ребром в v n .$v_n$$v_n$$v_n$$v_n$

Для каждой другой вершины , идущей от конца назад, сначала добавьте v i к своему собственному транзитивному замыканию, затем добавьте все в транзитивном замыкании v i к транзитивному замыканию всех вершин с ребром к v i .$v_i$$v_i$$v_i$$v_i$

Время выполнения в худшем случае с n числом вершин и m ∈ O ( n 2 ) числом ребер. Топологическая сортировка занимает время O ( n + m ) . Затем мы выполняем еще одну O ( m n ) работу в обратном проходе: когда мы идем назад по списку, для каждого ребра мы должны добавить до $O(n+m+nm) = O(n^3)$$n$$m \in O(n^2)$$O(n+m)$$O(mn)$$n$ вершины к чьему-то транзитивному замыканию.

Обратите внимание, что вы можете получить хорошее ускорение с постоянным коэффициентом, представляя транзитивное замыкание каждого с помощью битовых массивов. Скажем, у вас было только ; тогда вы бы использовали один 64-битный тип int, где бит i равен 1, если i находится в моем транзитивном замыкании, и 0 в противном случае. Тогда та часть , где мы добавляем все в я «s транзитивного замыкания на J » S очень быстро: Мы просто взять гр J | = с я . (Двоичная операция ИЛИ.)$n=64$$i$$i$$i$$j$$c_j$$c_i$

Для вам придется хранить их в массивах и выполнять некоторую арифметику, но это будет намного быстрее, чем набор объектов.$n > 64$

$O$$O(n^3)$