2

このSO 投稿に出くわしました。有向グラフで DFS を使用したサイクル検出は、バックトラッキングのために高速であることが示唆されています。ここで私はそのリンクから引用します：

深さ優先検索は、幅優先検索よりも早くバックトラックできるため、メモリ効率が高くなります。コール スタックを使用すると実装も簡単になりますが、これはスタックをオーバーフローしない最長パスに依存します。

また、グラフが方向付けされている場合は、ノードにアクセスしたかどうかだけでなく、どのようにしてそこに到達したかを覚えておく必要があります。そうでなければ、サイクルを見つけたと思うかもしれませんが、実際には 2 つの別個のパス A->B しかありませんが、それはパス B->A があるという意味ではありません。深さ優先検索を使用すると、下降するときにノードを訪問済みとしてマークし、バックトラックするときにそれらのマークを解除できます。

バックトラックが不可欠な理由

与えられた例で何を意味するのか、誰かが例のグラフで説明できますかA->B?

最後に、DFSバックトラッキングを使用しない有向グラフでのサイクル検出のコードがありますが、それでもサイクルで検出されO(E+V)ます。

public boolean isCyclicDirected(Vertex v){
  if (v.isVisited) {
    return true;
  }
  v.setVisited(true);
  Iterator<Edge> e = v.adj.iterator();
  while (e.hasNext()) {
    Vertex t = e.next().target;
    // quick test:
    if (t.isVisited) {
      return true;
    }
    // elaborate, recursive test:
    if (isCyclicDirected(t)) {
      return true;
    }
  }
  // none of our adjacent vertices flag as cyclic
  v.setVisited(false);
  return false;
}
4

3 に答える 3

5

バックトラックが必要な理由:

A -> B
^ \
|  v
D <- C

行っA -> Bて後戻りしないと、そこで止まり、サイクルを見つけることができなくなります。

あなたのアルゴリズムはバックトラックします。再帰でラップしているだけなので、期待どおりに見えない場合があります。これがサイクルを見つけられない場合、その呼び出しが戻り、他のネイバーを試します-これはバックトラックです。

現在の場所に到達した方法を覚えておく必要がある理由:

A -> B
  \  ^
   v |
     C

上のグラフにはサイクルがありませんが、パスを覚えていなくても、 、 、 と行けばあると思いますA -> B。A -> C -> B

リンクされた投稿で述べたように、コードに戻る前に、visited フラグを false に設定するだけで済みます (これで完了です)。これは、パスを覚えているように機能します。

于 2013-12-12T22:22:01.653 に答える