# Finding reachable vertices

I'm trying to solve a graph problem ( it's not for homework, just to practise 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_i$ is a set containing all the connections of $i$.

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 an other way ( with better complexity ) to solve the transitive closure problem in a dag? Thanks in advance.

• What is $f(\cdot)$? – Dimitris Dec 6 '12 at 18:18
• @JɛﬀE Sorry I edited it. I misunderstood what the blog said. – Rontogiannis Aristofanis Dec 6 '12 at 18:45
• i think this is for cs@stackexchange – Sasho Nikolov Dec 6 '12 at 19:28
• Check this out: sciencedirect.com/science/article/pii/0304397588900321 – George Dec 6 '12 at 20:57
• @Kaveh isn't the problem exactly transitive closure here? – Sasho Nikolov Dec 13 '12 at 8:26

Here is an $O(VE)$ algorithm, which is substantially better than $O(V^3)$ if the graph is sparse. First do a topological sort, in time $O(V+E)$. Now work your way backwards, storing which vertices are reachable. At a vertex of outdegree $d$, this requires $O(dV)$ work, so in total you get $O(VE)$.