17

だから私はRobert SedgewickのAlgorithms 4th edを読んでいます。本と有向グラフでサイクルを見つける方法は、無向グラフでサイクルを見つける方法とは異なります。

無向グラフでサイクルを見つけるためのコード例を次に示します

public class Cycle {
   public boolean[] marked;
   public boolean hasCycle;

   public Cycle(Graph G) {
      marked = new boolean[G.V()]; // G.V() is the number of vertices in the graph G
      for (int s = 0; s < G.V(); ++s) {
         if (!marked[s])
            dfs(G, s, s);
      }
   }

   private void dfs(Graph G, int v, int u) {
      marked[v] = true;
      for (int w : G.adj(v)) //iterate through vertices adjacent to v
         if (!marked[w])
            dfs(G, w, v)
         else if (w != u) hasCycle= true;
   }

   public boolean hasCycle() {
      return hasCycle;
   }
}

ただし、有向グラフでサイクルを見つけようとするとき、Sedgewick は、現在の呼び出しスタック中に i 番目の頂点が調べられた場合、その配列の i 番目の要素が true であるブール配列を使用します。検査された頂点 K ごとに、ブール配列の K 番目の要素が true かどうかを確認します。もしそうなら、私たちはサイクルを持っています。私の質問は、有向グラフにそのブール配列を使用する必要があるのはなぜですか。リストしたばかりのアプローチは、よりメモリ効率が良いのではないでしょうか? そして、このアプローチは無向グラフに対してのみ機能しますか? なぜ？

4

1 に答える 1

32

同じアルゴリズムを使用することはできません。上記のアルゴリズムは、グラフのすべての接続されたコンポーネントを探索するだけです。既にマークされた頂点に遭遇した場合、そこに到達するには2 つの異なるパスが必要であり、無向グラフにはサイクルが存在する必要があります。そうでない場合は、次の接続されたコンポーネントに進むことができます。完了したばかりのコンポーネントをクリーンアップする必要はありません。

一方、有向グラフがある場合、同じ頂点への 2 つの異なるパスは循環しません。そのため、別のアルゴリズムが必要です (たとえば、バックトラックしたステップをクリーンアップする必要がある場合があります)。

于 2012-06-10T20:35:25.070 に答える