深さ優先検索中に系図グラフでサイクルを検出する

StackOverflow https://stackoverflow.com/questions/621229

質問

馬の系譜データを再帰的にロードしています。 間違ったデータセットの場合、再帰が停止することはありません...これは、データにサイクルがあるためです。

繰り返しを停止するためにこれらのサイクルを検出するにはどうすればよいですか

定期的にすべての「訪問済み」のhashTableを維持することを考えました。馬。 しかし、馬は木に2回入ることができるため、誤検知が発生します。

起こり得ないことは、馬がITSELFの父親、祖父、またはgreat祖父として登場することです。

役に立ちましたか？

解決

擬似コード：

void ProcessTree(GenTreeNode currentNode, Stack<GenTreeNode> seen)
{
   if(seen.Contains(currentNode)) return;
   // Or, do whatever needs to be done when a cycle is detected

   ProcessHorse(currentNode.Horse); // Or whatever processing you need

   seen.Push(currentNode);

   foreach(GenTreeNode childNode in currentNode.Nodes)
   {
      ProcessTree(childNode, seen);
   }

   seen.Pop();
}

基本的な考え方は、現在のノードに至るまでに見たすべてのノードのリストを保持することです。既に通過したノードに戻った場合、サイクルを形成していることがわかります（値をスキップするか、必要なことは何でも行う必要があります）

他のヒント

ツリーのルートまでのすべての要素のスタックを維持します。

ツリーを下に進むたびに、子要素のスタックをスキャンします。一致するものが見つかった場合、ループを発見したため、その子をスキップする必要があります。それ以外の場合は、子をスタックにプッシュして続行します。ツリーをバックトラックするたびに、スタックから要素をポップして破棄します。

（系図データの場合、ツリー内の「子」ノードは、おそらく「親」ノードの生物学的親です。）

これは、面接トリビアの質問を最終的に適用できるケースのように聞こえます。O（1）メモリのみを使用してリンクリストでサイクルを見つけます。

この場合、「リンクリスト」列挙する要素のシーケンスです。 2つの列挙子を使用し、一方を半分の速度で実行します。高速の列挙子が低速の列挙子にぶつかるとループが発生します。これは、「表示済み」リストのチェックに必要なO（n ^ 2）時間ではなく、O（n）時間にもなります。欠点は、ノードの一部が複数回処理された後にのみループについて知ることです。

この例では、「ハーフスピード」メソッドを、より簡単に記述できる「ドロップマーカー」メソッドに置き換えました。

class GenTreeNode {
    ...

    ///<summary>Wraps an the enumeration of linked data structures such as trees and linked lists with a check for cycles.</summary>
    private static IEnumerable<T> CheckedEnumerable<T>(IEnumerable<T> sub_enumerable) {
        long cur_track_count = 0;
        long high_track_count = 1;
        T post = default(T);
        foreach (var e in sub_enumerable) {
            yield return e;
            if (++cur_track_count >= high_track_count) {
                post = e;
                high_track_count *= 2;
                cur_track_count = 0;
            } else if (object.ReferenceEquals(e, post)) {
                throw new Exception("Infinite Loop");
            }
        }
    }

    ...

    ///<summary>Enumerates the tree's nodes, assuming no cycles</summary>
    private IEnumerable<GenTreeNode> tree_nodes_unchecked() {
        yield return this;
        foreach (var child in this.nodes)
            foreach (var e in child.tree_nodes_unchecked())
                yield return e;
    }
    ///<summary>Enumerates the tree's nodes, checking for cycles</summary>
    public IEnumerable<GenTreeNode> tree_nodes()
    {
        return CheckedEnumerable(tree_nodes_unchecked());
    }

    ...

    void ProcessTree() {
        foreach (var node in tree_nodes())
            proceess(node);
    }
}

これを検出する非常に簡単な方法は、その制約自体をチェックすることです：

  

起こり得ないことは、馬がITSELFの父親、祖父、またはgreat祖父として登場することです。

ツリーにノードを挿入するたびに、ツリーをルートまでトラバースして、馬が親として存在しないことを確認します。

これを高速化するために、ハッシュテーブルを各ノードに関連付けて、そのようなルックアップの回答をキャッシュできます。次に、そのノードの下に馬を挿入するときにパス全体を検索する必要はありません。

馬ではなくノードを追跡する場合、ハッシュテーブルソリューションは動作するはずです。値/馬が前のノードの値/馬と同じであっても、新しい馬を読むたびに新しいノードを作成するようにしてください。

あなたは、ツリーではなく、有向非巡回グラフを扱っています。馬の子孫がその祖先になることはできないため、サイクルはありません。

これを知っているので、有向非巡回グラフに固有のコード手法を適用する必要があります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top