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

Question

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

これらのサイクルを検出して再発を止めるにはどうすればよいですか?

私は、すべての「訪問した」馬でハッシュテーブルを定期的に維持することを考えました。しかし、馬は木に2回いる可能性があるため、いくつかの誤検知が見つかります.

あり得ないことは、馬が ITSELF の父または祖父または曽祖父として現れることです。

Answer 1

これは、インタビューのトリビアの質問を最終的に適用できるケースのように思えます: 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);
    }
}