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.

Answer 2

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.