Wydajny algorytm odzyskiwania przejściowego zamknięcia ukierunkowanego wykresu acyklicznego

Próbuję rozwiązać problem z grafem (nie jest to praca domowa, tylko po to, aby ćwiczyć swoje umiejętności). Podaje się DAG , gdzie jest zbiorem wierzchołków, a krawędziami. Wykres jest reprezentowany jako lista przylegania, więc jest zbiorem zawierającym wszystkie połączenia . Moim zadaniem jest znalezienie których wierzchołki są osiągalne z każdego wierzchołka . Rozwiązanie, którego używam, ma złożoność , z przejściowym zamknięciem, ale czytam, że na blogu może być szybsze, chociaż nie ujawniało, jak to zrobić. Czy ktoś mógłby mi powiedzieć inny sposób (z większą złożonością), aby rozwiązać problem przejścia przechodniego w DAG?V E A v v v ∈ V O ( V 3$G(V,E)$$V$$E$$A_v$$v$$v\in V$$O(V^3)$

Fakt, że nasz wykres jest acykliczny, znacznie upraszcza ten problem.

Sortowanie topologiczne może dać nam uporządkowanie wierzchołków tak, że jeśli i < j , to nie ma krawędzi od v j z powrotem do v i . Wymieniliśmy wierzchołki tak, aby wszystkie krawędzie były „do przodu” na naszej liście.$v_1,v_2,\dots,v_n$$i < j$$v_j$$v_i$

(edytowane w celu naprawy analizy i nieco szybszego algorytmu)

Teraz przechodzimy do tyłu przez tę listę, zaczynając od ostatniego wierzchołka . Zamknięcie przechodnie v n jest po prostu samo w sobie. Dodaj także v n do przejściowego zamknięcia każdego wierzchołka z krawędzią do v n .$v_n$$v_n$$v_n$$v_n$

Dla każdego innego wierzchołka , idąc od końca do tyłu, najpierw dodaj v i do własnej przechodniego zamknięcia, a następnie dodać wszystko w przechodniego zamknięcia v í do przechodniego zamknięciu wszystkie wierzchołki z krawędzią do V í .$v_i$$v_i$$v_i$$v_i$

Czas pracy wynosi w najgorszym przypadku, przy n liczbie wierzchołków i m ∈ O ( n 2 ) liczbie krawędzi. Sortowanie topologiczne zajmuje czas O ( n + m ) . Następnie wykonujemy kolejną pracę O ( m n ) w przejściu wstecznym: Gdy przeglądamy listę do tyłu, dla każdej krawędzi musimy dodać do $O(n+m+nm) = O(n^3)$$n$$m \in O(n^2)$$O(n+m)$$O(mn)$$n$ wierzchołki do kogoś przechodnie przechodnie.

Zauważ, że możesz uzyskać ładne przyspieszenie o stałym współczynniku, reprezentując przechodnie przechodzenie wszystkich przez tablice bitów. Powiedzmy, że miałeś tylko ; wtedy użyłbyś pojedynczego 64-bitowego int, gdzie bit i ma wartość 1, jeśli i jest w moim przejściowym zamknięciu, a 0 w przeciwnym razie. Następnie część, gdzie możemy dodać wszystko í „s przechodniego zamknięciem j ” s jest bardzo szybki: Po prostu wziąć c j | = c i . (Operacja binarna LUB.)$n=64$$i$$i$$i$$j$$c_j$$c_i$

Dla musielibyście trzymać je w tablicach i wykonywać arytmetykę, ale byłoby to znacznie szybsze niż zestaw obiektów.$n > 64$

Wiem też, że duże- w najgorszym przypadku to wciąż O ( n 3 ) , ale aby pokonać to w praktyce, musiałbyś mieć coś znacznie bardziej złożonego. Algorytm ten działa również bardzo dobrze na rzadkich grafach.$O$$O(n^3)$