HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Efficient algorithm for retrieving the transitive closure of a directed acyclic graph

Submitted by: @import:stackexchange-cs··
0
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.

Context

StackExchange Computer Science Q#7231, answer score: 12

Revisions (0)

No revisions yet.