0

I am trying to retrieve all possible paths based on some conditions from source to destination using iterative depth-first search (not recursion). I already solved the problem using recursion.

Now, I am wondering if we can retrieve all paths in an undirected graph from source to destination without help of recursion..

Can you please help me clarify and explain me what I should do to this problem? Or do you need to stick with recursion for the ease?

Liu Bei
  • 565
  • 3
  • 9
  • 19
  • Yes, you can. See an [example here](https://stackoverflow.com/a/51048109/3992939) and [here](https://stackoverflow.com/a/48718818/3992939) (the last one is BSF but the technique is identical). In fact, [every recursive function can be turned into a recursive one](https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration). – c0der Dec 30 '21 at 04:59

1 Answers1

-1

I'd say you can't do what you are asking even with recursion ... the question does not restrict the graph to being acyclic, and it is undirected, so the simplest counterexample would be two nodes, A and B and if you remove "acyclic" and directed from the graph, there are infinite paths from A to B by extending the depth infinitely.

If the graph is acyclic, the answer becomes yes, even if you use a brute force method. The breadth first search would be the obvious counterpart to DFS.

Brian Withnell
  • 31
  • 6
  • [every recursive function can be turned into a recursive one](https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration) – c0der Dec 30 '21 at 05:02
  • That is true, but the problem is not solvable in the general sense. My example was two nodes A and B. To get from A to B you have a path that is direct ... "A->B" one that cycles on A any number of times "A->A->A->A->B" which is a different path. The problem actually has no finite answer. What I'm saying his DFS recursive solution cannot be correct. – Brian Withnell Dec 30 '21 at 05:23
  • If you allow an edge from a node to itself any number of times, which means an infinite number of paths, the recursion should run until it overflows and an iterative solution should run forever. Both techniques need an appropriate stop condition. – c0der Dec 30 '21 at 07:27
  • Exactly. The problem as stated doesn't have well defined end conditions. – Brian Withnell Dec 30 '21 at 14:37