0

有向グラフの 2 つのノード間のすべての可能なパスを出力するアルゴリズムを探していました。

これを見た ：

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

しかし、実行すると、正しいパスが出力され、無限ループに入り、そのパスが出力されます!! どうしたの ？

特別な感謝、

4

1 に答える 1

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);
于 2013-01-01T11:49:24.340 に答える