グラフ問題のアルゴリズム

Question

リスト内の指向性ノードの接続性をチェックする必要があります。 基本的に2〜7つの回答を持つ質問です。選択された答えが次の質問を指示します。 これらのペアは手動でキャプチャされるため、ループバック（許可されない）とデッドエンド（すべてのルートがENDノードで停止する必要があります）の可能な各パスを確認する必要があります すべてのポインタ？

start --> n1 --- n2 --- n3 --- n4 --- end 

      \/ \  \ / /

      n5  \  n6------ n7 

       \  \ / /

       n8----n9---n10----n11 

      DIRECTION --> 

Answer 1

これは、あなたが探しているものかもしれ：

Testing whether a graph is acyclic

エンド・ノードは、リーフノードは、そのページの用語であるものです。

1. グラフにノードがない場合は、非循環です。
2. グラフにリーフがない場合、それは循環します。
3. は、任意の葉を選択してデッドエンドを存在しないことを確認するには、葉とそれへのすべての遷移、後藤ステップ1

を削除します。単純に上記のアルゴリズムを使用する前に、単一のリーフノードがあることを確認してください。

Answer 2

すでに訪問したノードのすべてのトラックを保つこと、breadth first searchアルゴリズムを使用してください。次のノードを探索するときに既に訪れたノードの1つが可能性がある場合、グラフは間違っています。さらに、次のノードに到達する可能性のあるノードがなく、まだ到達していないノードに到達すると、グラフも正しく接続されません。