0
$\begingroup$

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?

enter image description here

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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ I don't understand what you mean by "inputs" or "neuron". $\endgroup$
    – D.W. ♦
    Commented Apr 30, 2020 at 7:42
  • $\begingroup$ The representation of the directed graph in memory is recursive, each node has a set of inputs. $\endgroup$
    – Tobi
    Commented Apr 30, 2020 at 7:44
  • $\begingroup$ Rather than responding in the comments, please edit the question to clarify. Please either avoid using $n$, or define what it represents in the question. I see the question still uses $n$. I don't know what it means to say that the representation is recursive, and I still don't know what it means for a node to have inputs. Do you mean incoming edges? $\endgroup$
    – D.W. ♦
    Commented Apr 30, 2020 at 7:47

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ DFS works if you can traverse a nodes outputs, in constant time. As explained, only the inputs can be traversed (In constant time) $\endgroup$
    – Tobi
    Commented Apr 30, 2020 at 7:36
  • $\begingroup$ Do you think this is optimal? $\endgroup$
    – Tobi
    Commented Apr 30, 2020 at 7:39
  • $\begingroup$ Inversion of a graph (to prepare for DFS) works in $O(E)$ time, and DFS obviously works in $O(V+E)$. The spacial complexity however is now $O(V^2)$ as an inverted graph is (briefly) stored in memory. $\endgroup$
    – Tobi
    Commented Apr 30, 2020 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.