What time complexity is a reachability algorithm? I've read there are ways you can determine all reachable pairs using Strongly Connected Components. But, I want to calculate all reachable nodes on the fly - so I don't have to store a massive reachability matrix in RAM. What sort of time complexity would be possible for an algorithm to calculate all reachable nodes in a directed graph, from a single node?



Here's a naive algorithm I came up with, I'm not sure of the time complexity of this. $O(V!)$?

It seems to have an $O(V)$ spacial complexity though.

I've read about the Bellman-Ford algorithm with a time complexity of $O(EV)$ which is essentially $O(V^3)$ and the Floyd-Warshall algorithm which is $O(V^3)$. They require $O(V)$ and $O(V^2)$ space complexity, respectively.

The problem is only inputs can be determined in constant time. So, one would have to find (in $O(V)$ time)  all outputs for a particular node. What I actually did in my solution is invert the graph using a similar technique, before running DFS. But I don't know if this is optimal... Also, due to a copy of the graph being stored in memory, my solution has a spacial complexity worse than the bellman-ford algorithm. If this time complexity is also worse, I may as well use bellman fords algorithm
You can calculate all reachable nodes in $O(V+E)$ time and $O(V)$ space, using DFS on the fly.

If you want to use less than $O(V)$ space, then the problem becomes much more challenging.  I recommend looking at how the SPIN model checker works.  See https://en.wikipedia.org/wiki/Bitstate_hashing.  Even then, the space required is probably still $O(V)$, just with a lower constant factor.