patternModerate
Efficient algorithm for retrieving the transitive closure of a directed acyclic graph
Viewed 0 times
thegraphacyclicefficientdirectedtransitivealgorithmforretrievingclosure
Problem
I'm trying to solve a graph problem (it's not for homework, just to practice my skills). A DAG $G(V,E)$ is given, where $V$ is the set of vertices and $E$ the edges. The graph is represented as an adjacency list, so $A_v$ is a set containing all the connections of $v$. My task is to find which vertices are reachable from each vertex $v\in V$. The solution I use has a complexity of $O(V^3)$, with transitive closure, but i read that in a blog it can be faster, although it didn't reveal how. Could anyone tell me another way (with better complexity) to solve the transitive closure problem in a DAG?
Solution
The fact that our graph is acyclic makes this problem much simpler.
Topological sort can give us an ordering of the vertices $v_1,v_2,\dots,v_n$ such that, if $i 64$, you'd have to keep them in arrays and do some arithmetic, but it would be much faster than an Object set.
Also, I know the big-$O$ in the very worst case is still $O(n^3)$, but to beat this in practice you'd have to have something much more complex. This algorithm also does very well on sparse graphs.
Topological sort can give us an ordering of the vertices $v_1,v_2,\dots,v_n$ such that, if $i 64$, you'd have to keep them in arrays and do some arithmetic, but it would be much faster than an Object set.
Also, I know the big-$O$ in the very worst case is still $O(n^3)$, but to beat this in practice you'd have to have something much more complex. This algorithm also does very well on sparse graphs.
Context
StackExchange Computer Science Q#7231, answer score: 12
Revisions (0)
No revisions yet.