I have a graph like this that starts from one top node and has cycles:
I need to write an algorithm to figure if
node1 depends on
node2. The most primitive algorithm I’ve written simply starts with
node1 and recursively follows all available edges looking for
node2 starting from
node1. It’s very inefficient because I traverse the graph over and over again. I’m wondering if there’s an algorithm I can look at that caches nodes and dependencies it already walked through so that I don’t go through paths I’ve walked once and can figure if there’s a dependency or not from cache?
For example, if I’m given node
D and the question is whether it depends on node
F, I’ll walk
D->E->F, and when next time I get the question if node
E depends on
F, I’ll get that from cache without walking the graph.
Thanks for any ideas and suggestions!