algorithm - 两点间简单路径的非递归DFS算法

Question

我正在寻找一种非递归深度优先搜索算法来查找无向图中两点之间的所有简单路径(循环是可能的)。

我查了很多帖子，都是递归算法。似乎没有人对非递归版本感兴趣。

递归版本是这样的；

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;
}

所以，我试过它(非递归)，但是当我检查它时，它计算错了

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();
  }

测试图为:

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

它是无向的，这就是为什么有 (a,b) 和 (b,a)。如果开始和结束节点是'a'和'h'，那么应该有两条简单的路径:

a,b,c,f,h

a,b,d,f,h.

但该算法无法找到两者。它显示输出为:

a,b,d,f,h,

a,b,d.

堆栈成为第二条路径的开始，这就是问题所在。将其更改为非递归版本时请指出我的错误。您的帮助将不胜感激!

Answer 1

我认为 dfs 是一个非常复杂的算法，尤其是在其迭代形式中。迭代版本最重要的部分是洞察力，在递归版本中，不仅当前节点，而且当前邻居都存储在堆栈中。考虑到这一点，在 C++ 中，迭代版本可能如下所示:

//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);
         }      
      }
  }
}

不保证它没有错误，但我希望你明白要点，至少它在你的例子中找到了两条路径。