深さ優先探索中の系図のサイクルを検出する

Question

馬の系図データを再帰的にロードしています。 いくつかの間違ったデータセットに対して、私の再帰は決して止まらない...それはデータにサイクルがあるからです。

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

私は、すべての「訪問済み」馬のhashTableを定期的に維持していると考えました。 しかし、それは馬が木の中で2回あることがあるので、いくつかの偽陽性を見つけるでしょう。

馬は、ITSELFの祖父または祖父または曾祖父として現れることはありません。

Answer 1

擬似コード：

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(); 
} 

基本的な考え方は、我々はすでにダウンし、現在のノードへ行く途中に見てきたすべてのノードのリストを維持することです。既に完了したノードに戻った場合は、サイクルが形成されていることがわかります（値をスキップするか、実行する必要があるものはすべて実行してください）。

Answer 2

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

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

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

Answer 3

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

馬は、ITSELFの父または祖父またはgreatgrandfatherとして表示されることはできません。

ノードをノードに挿入するときは、ツリーをルートにトラバースして、馬がどのような種類の親としても存在しないことを確認します。

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

Answer 4

ハッシュテーブルの解決策は、あなたは馬の代わりにノードを追跡します。値/馬が前のノードの値/馬と同じであっても、新しい馬を読むたびに必ず新しいノードを作成するようにしてください。

Answer 5

あなたはツリーではなくdirected acyclic graphを扱っています。馬の子孫もその祖先になることができないので、サイクルがあってはいけません。

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

Answer 6

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

この場合、リンクされたリストは列挙する要素のシーケンスです。2つの列挙子を使用し、1つは半分の速度で実行し、速いものが遅いものに実行される場合は、ループがあります。また、これは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); 
    } 
}