computer-science - 这个 FindAllPath 算法在有向图中是否正确？

Question

我正在寻找一种算法来打印有向图中两个节点之间的所有可能路径。

我看到了这个 ：

    procedure FindAllPaths(u, dest)
{
   push u to stack;
   if(u == dest)
   {
      print stack;
   }
   else
   {
      foreach v that is adjacent with u and not in stack now
      {
         FindAllPaths(v, dest);
      }
   }
   pop from stack;
}

但是当我运行它时，它会打印出正确的路径并进入无限循环并打印出该路径！有什么问题 ？

特别感谢，

Answer 1

这是您的算法的 JavaScript 实现，带有示例图。它在这里工作。如果您发现您的实施有所不同，请发布更多信息：

var edges = [
    {from:0, to:0},
    {from:0, to:1},
    {from:0, to:2},
    {from:1, to:3},
    {from:2, to:3},
    {from:2, to:0}
];

var stack = [];

function FindAllPaths(u, dest) {
    stack.push(u);
    if(u === dest)
    {
        console.log(stack.join('->'));
    }
    else
    {
        for(i in edges) {
            var edge = edges[i];
            if (edge.from == u && stack.indexOf(edge.to) < 0) {
                FindAllPaths(edge.to, dest);
            }
        }
    }
    stack.pop();
}

FindAllPaths(0, 3);