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!