In general this is basically a traversal algorithm that’s going through directed cyclical graph (if you don’t allow cycles then directed acyclical graph or DAG). We know we have:
- Breath-First
- Depth-First
These just differ by using a queue instead of a stack to store the current traversed nodes. You also need to keep a list of visited nodes to avoid infinite loop. You really don’t need recursion as it is expensive for this algorithm. Here’s a break down in pseudo-code
- Put root node into Stack/Queue
- While Stack/Queue is not empty, Do:
- Pop or Dequeue a node
- Do work and add this to the visited list
- for each of its connected node, push it or enqueue it
Since you are looking for path, depth first will give you a single path at a time while breath first will give you all path incrementally.