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?
Tell me more
×
Computer Science Stack Exchange is a question and answer site for
students, researchers and practitioners of computer science. It's 100% free, no registration required.
|
|
|||||||||||||
|
|
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 < j$, then there is no edge from $v_j$ back to $v_i$. We've listed the vertices such that all edges in go "forward" in our list. (edited to fix analysis and give slightly faster algorithm) Now we just go backwards through this list, starting at the last vertex $v_n$. $v_n$'s transitive closure is just itself. Also add $v_n$ to the transitive closure of every vertex with an edge to $v_n$. For each other vertex $v_i$, going from the end backwards, first add $v_i$ to its own transitive closure, then add everything in the transitive closure of $v_i$ to the transitive closure of all the vertices with an edge to $v_i$. The running time is $O(n+m+nm) = O(n^3)$ in the worst case, with $n$ the number of vertices and $m \in O(n^2)$ the number of edges. Topological sort takes time $O(n+m)$. Then we do another $O(mn)$ work in the backward pass: As we go backwards through the list, for each edge, we have to add up to $n$ vertices to somebody's transitive closure. Note that you can get a nice constant-factor speedup by representing everyone's transitive closure by bit-arrays. Say you only had $n=64$; then you would use a single 64-bit int where bit $i$ is 1 if $i$ is in my transitive closure and 0 otherwise. Then the part where we add everything in $i$'s transitive closure to $j$'s is really fast: We just take $c_j$ |= $c_i$. (Binary OR operation.) For $n > 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. |
||||
|
|
