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!

Answer 1

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.