Non recursive DFS algorithm for simple paths between two points

Question

I am looking for a non-recursive Depth first search algorithm to find all simple paths between two points in undirected graphs (cycles are possible).

I checked many posts, all showed recursive algorithm. seems no one interested in non-recursive version.

a recursive version is like this;

void dfs(Graph G, int v, int t) 
{
   path.push(v);
   onPath[v] = true;
   if (v == t)
   {
     print(path);
   }
   else 
   {
    for (int w : G.adj(v))
    {
        if (!onPath[w])
            dfs(G, w, t);
    }
   }
  path.pop();
  onPath[v] = false;
}

so, I tried it as (non-recursive), but when i check it, it computed wrong

void dfs(node start,node end) 
{
   stack m_stack=new stack();
   m_stack.push(start);
   while(!m_stack.empty)
   {
       var current= m_stack.pop();
       path.push(current);
      if (current == end)
      {
          print(path);
      }
      else 
      {
        for ( node in adj(current))
        {
            if (!path.contain(node))
               m_stack.push(node);
        }
      }
     path.pop();
  }

the test graph is:

(a,b),(b,a), (b,c),(c,b), (b,d),(d,b), (c,f),(f,c), (d,f),(f,d), (f,h),(h,f).

it is undirected, that is why there are (a,b) and (b,a). If the start and end nodes are 'a' and 'h', then there should be two simple paths:

a,b,c,f,h

a,b,d,f,h.

but that algorithm could not find both. it displayed output as:

a,b,d,f,h,

a,b,d.

stack become at the start of second path, that is the problem. please point out my mistake when changing it to non-recursive version. your help will be appreciated!

Possible duplicate of [Non recursive Depth first search algorithm](http://stackoverflow.com/questions/5278580/non-recursive-depth-first-search-algorithm) — Tamas Ionut, Feb 03 '16 at 08:39
I tried, but having problem with correcting current path, so second path will be wrong. i think I am wrong at somewhere, so help — arslan, Feb 03 '16 at 09:29
What you posted as an answer (the code and what went wrong) should actually be a part of your question. Also, please format the code properly (four spaces at the start of each line) and tell us what exactly went wrong. The phrase "it computed wrong" does not tell us what you expected and what you got instead. — Gassa, Feb 03 '16 at 09:45
It would be interesting to know, why you like the iterative version more. — ead, Feb 03 '16 at 20:50
I prefer iterative because graph could be really large and i want to add some computation on current sometimes. I thought iterative will be easier to follow for me. — arslan, Feb 04 '16 at 05:31
If the graph is really large, than you have a problem: there are O(n!) possible paths - it will be slow no matter which version you take. — ead, Feb 04 '16 at 08:05
@alim Does your recursive version still manage to print out all simple paths? — RoadRunner, Mar 25 '17 at 04:13

ead · Accepted Answer · 2017-03-25T08:08:58.287

I think dfs is a pretty complicated algorithm especially in its iterative form. The most important part of the iterative version is the insight, that in the recursive version not only the current node, but also the current neighbour, both are stored on the stack. With this in mind, in C++ the iterative version could look like:

//graph[i][j] stores the j-th neighbour of the node i
void dfs(size_t start, size_t end, const vector<vector<size_t> > &graph) 
{

   //initialize:
   //remember the node (first) and the index of the next neighbour (second)
   typedef pair<size_t, size_t> State;
   stack<State> to_do_stack;
   vector<size_t> path; //remembering the way
   vector<bool> visited(graph.size(), false); //caching visited - no need for searching in the path-vector 


   //start in start!
   to_do_stack.push(make_pair(start, 0));
   visited[start]=true;
   path.push_back(start);

   while(!to_do_stack.empty())
   {
      State &current = to_do_stack.top();//current stays on the stack for the time being...

      if (current.first == end || current.second == graph[current.first].size())//goal reached or done with neighbours?
      {
          if (current.first == end)
            print(path);//found a way!

          //backtrack:
          visited[current.first]=false;//no longer considered visited
          path.pop_back();//go a step back
          to_do_stack.pop();//no need to explore further neighbours         
      }
      else{//normal case: explore neighbours
          size_t next=graph[current.first][current.second];
          current.second++;//update the next neighbour in the stack!
          if(!visited[next]){
               //putting the neighbour on the todo-list
               to_do_stack.push(make_pair(next, 0));
               visited[next]=true;
               path.push_back(next);
         }      
      }
  }
}

No warranty it is bug-free, but I hope you get the gist and at least it finds the both paths in your example.

Great, finally i have the answer. I used 'for' statement and put all neighbors at once, that is why i could not go back once find a path. thank you very much. — arslan, Feb 04 '16 at 05:55
the delicate part I think is how to remember the visited neighbors of current node. it seems this algorithm might research already explored paths. well, non-recursive surely complicated. — arslan, Feb 04 '16 at 06:32

score 0 · Answer 2 · answered Feb 03 '16 at 10:31

The path computation is all wrong. You pop the last node before you process it's neighbors. Your code should output just the last node.

The simplest fix is to trust the compiler to optimize the recursive solution sufficiently that it won't matter. You can help by not passing large objects between calls and by avoiding allocating/deallocating many objects per call.

The easy fix is to store the entire path in the stack (instead of just the last node).

A harder fix is that you have 2 types of nodes on the stack. Insert and remove. When you reach a insert node x value you add first remove node x then push to the stack insert node y for all neighbours y. When you hit a remove node x you need to pop the last value (x) from the path. This better simulates the dynamics of the recursive solution.

A better fix is to just do breadth-first-search since that's easier to implement in an iterative fashion.

"path computation is all wrong", yes, I think so, I need an idea to fix it. I have only one kind of nodes. so how can i construct correct simple paths ? — arslan, Feb 03 '16 at 13:13

Non recursive DFS algorithm for simple paths between two points

2 Answers2