26

有向グラフが循環的かどうかをどのように検出できますか? 幅優先探索をしようと思ったのですが、よくわかりません。何か案は？

4

6 に答える 6

16

本当に必要なのは、ここで説明されているようなトポロジカル ソート アルゴリズムだと思います。

http://en.wikipedia.org/wiki/Topological_sorting

有向グラフにサイクルがある場合、アルゴリズムは失敗します。

私がこれまでに見たコメント/返信は、有向グラフでは、グラフに (有向) サイクルがなくても、ノード X からノード Y に到達する方法が複数ある可能性があるという事実を見逃しているようです。

于 2010-03-29T17:11:22.903 に答える
13

通常、代わりに深さ優先検索が使用されます。BFSが簡単に適用できるかどうかはわかりません。

DFSでは、訪問順にスパニング ツリーが構築されます。ツリー内のノードの祖先にアクセスすると (バックエッジが作成された場合)、サイクルが検出されます。

詳細な説明については、http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdfを参照してください。

于 2010-03-26T17:25:37.447 に答える
2

DFS を使用して、パスが循環しているかどうかを検索します

class Node<T> { T value; List<Node<T>> adjacent;  }

class Graph<T>{

    List<Node<T>> nodes;

   public boolean isCyclicRec()
   {

      for (Node<T> node : nodes)
      {
            Set<Node<T>> initPath = new HashSet<>();
            if (isCyclicRec(node, initPath))
            {
              return true;
            }
      }
      return false;
   }

   private boolean isCyclicRec(Node<T> currNode, Set<Node<T>> path)
   {
      if (path.contains(currNode))
      {
        return true;
      }
      else
      {
        path.add(currNode);
        for (Node<T> node : currNode.adjacent)
        {
            if (isCyclicRec(node, path))
            {
                return true;
            }
            else
            {
                path.remove(node);
            }
        }
      }
      return false;
  }
于 2014-08-15T00:43:45.047 に答える
1

アプローチ：1
サイクルを検出するレベルの割り当てはどうですか。例: 下のグラフを考えてみましょう。A->(B,C) B->D D->(E,F) E,F->(G) E->D DFS を実行すると、アクセスするノードにレベル no が割り当てられます (ルート A =0)。ノードのレベル番号 = 親 + 1。したがって、A=0、B=1、D=2、F=3、G=4 の場合、再帰は D に到達するため、E=3 になります。G のレベルをマークしないでください (G はすでに E よりも大きいレベルが割り当てられていません) E も D に対してエッジを持っています。したがって、レベライゼーションでは、D はレベル番号 4 を取得する必要があります。しかし、D には既に「より低いレベル」が割り当てられています。したがって、すでに低いレベル番号が設定されている DFS を実行しているときにノードにレベル番号を割り当てようとすると、有向グラフにサイクルがあることがわかります。

アプローチ 2:
3 色を使用します。白、グレー、黒。白のノードのみに色を付け、DFS を下るにつれて白のノードを灰色に、再帰が展開されると灰色のノードを黒に色付けします (すべての子が処理されます)。すべての子がまだ処理されておらず、サイクルである灰色のノードにヒットした場合。例: 上の直接グラフで始まるすべての白。カラー A、B、D、F、G はホワイトグレーに着色されています。G はリーフなので、すべての子はグレーから黒に色を処理します。再帰は F (処理されたすべての子) に展開され、色は黒になります。D に到達すると、D には未処理の子があるため、E はグレーに、G はすでに黒く着色されているため、それ以上下に移動しないでください。E にも D へのエッジがあるため、D を処理している間 (D はまだ灰色)、D に戻るエッジ (灰色のノード) が見つかり、サイクルが検出されます。

于 2012-04-06T21:19:49.230 に答える
0

特定のグラフでトポロジカル ソートをテストすると、解決策が得られます。トップソートのアルゴリズム、つまりエッジを常に一方向に向けるアルゴリズムが失敗した場合、グラフにサイクルが含まれていることを意味します。

于 2013-12-11T01:51:21.653 に答える
-1

もう1つの簡単な解決策は、マークアンドスイープアプローチです。基本的に、ツリー内のノードごとに、「訪問済み」としてフラグを立ててから、その子に移動します。「訪問済み」フラグが設定されたノードを目にしたことがあれば、サイクルがあることがわかります。

「訪問済み」ビットを含めるようにグラフを変更できない場合は、代わりにノードポインタのセットを使用できます。ノードに訪問済みのフラグを立てるには、ノードへのポインターをセットに配置します。ポインタがすでにセットに含まれている場合は、サイクルがあります。

于 2010-03-26T17:40:28.880 に答える