Detect-Zyklen in einer Genealogie Diagramm während einer Tiefensuche

Question

Ich bin Laden Pferdestammdaten rekursiv. Für einige falsche Datensätze meine Rekursion nie aufhört ... und das ist, weil es Zyklen in den Daten sind.

Wie kann ich erkennen, diese Zyklen wiederkehrenden zu stoppen?

Ich dachte an, während eine Hash-Tabelle mit allen halten wiederkehrenden „besuchten“ Pferde. Aber das wird einige Fehlalarme, weil ein Pferd zweimal in einem Baum werden kann.

Was nicht passieren kann, ist, dass ein Pferd als Vater oder Großvater oder Urgroßvater von mir selbst erscheinen.

Answer 1

Pseudo-Code:

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

Die Grundidee ist, eine Liste von allen Knoten zu halten, die wir bereits auf dem Weg gesehen haben nach unten auf den aktuellen Knoten; wenn zu einem Knoten war zurück, die wir bereits durchlief, dann wissen Sie, dass wir einen Zyklus gebildet haben (und wir sollten den Wert überspringen, oder tun, was getan werden muss)

Answer 2

Pflegen einen Stapel aller Elemente in die Wurzel des Baumes führt.

Jedes Mal, wenn Sie den Baum voran nach unten, scannen Sie den Stapel für das Kind-Element. Wenn Sie ein Spiel finden, dann haben Sie eine Schleife entdeckt und sollte das Kind überspringen. Andernfalls drücken Sie das Kind auf den Stapel und fortzufahren. Jedes Mal, wenn Sie den Baum Rückzieher up, Pop ein Element aus dem Stapel und entsorgen.

(Im Fall von Stammdaten, ein "Kind" Knoten in dem Baum ist vermutlich der biologische Elternteil der "parent" node).

Answer 3

Das klingt wie ein Fall, in dem man endlich das Interview Trivia Frage anwenden kann. Einen Zyklus in einer verknüpften Liste findet nur O (1) Speicher mit

In diesem Fall Ihre „verketteten Liste“ ist die Reihenfolge der Elemente, die Sie aufzuzählen. Verwenden Sie zwei Aufzählungen, führen eine mit halber Geschwindigkeit, und wenn der schnelle nie jemand in den langsamen läuft dann haben Sie eine Schleife. Dies wird auch O (n) Zeit anstelle der O (n ^ 2) Zeit zur Überprüfung einer ‚gesehen‘ Liste erforderlich sein. Der Nachteil ist, dass Sie nur über die Schleife herausfinden, nachdem einige der Knoten mehrfach verarbeitet wurden.

Im Beispiel habe ich ersetzt die halbe Geschwindigkeit "Methode mit dem einfacheren-to-write‚Drop-Marker‘-Methode.

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

Answer 4

Eine sehr einfache Möglichkeit, dies zu erkennen, ist durch diese Einschränkung Überprüfung selbst:

  

Was nicht passiert ist, dass ein Pferd als Vater oder Großvater oder Urgroßvater von mir selbst erscheinen.

Wenn Sie einen Knoten in Ihrem Baum einzufügen, durchquert den Baum an die Wurzel, um sicherzustellen, dass das Pferd nicht existiert als jede Art von Elternteil.

Um dies zu beschleunigen, können Sie eine Hash-Tabelle zu jedem Knoten zugeordnet werden können, in dem Sie die Antwort eines solchen Verweis-Cache. Dann sind Sie nicht den gesamten Weg zu suchen haben nächstes Mal, wenn Sie ein Pferd unter diesem Knoten eingefügt werden.

Answer 5

Ihre Hash-Tabelle Lösung sollte funktionieren, wenn Sie den Überblick über Knoten statt Pferde halten. So stellen Sie sicher, dass jedes Mal, wenn ein neues Pferd lesen erstellen Sie einen neuen Knoten, auch wenn der Wert / Pferd das gleiche wie ein vorhergehender Knoten Wert / Pferd ist.

Answer 6

Sie sind den Umgang mit einem azyklische Graph gerichtet, nicht auf einen Baum. Es sollte keine Zyklen sein, als Nachkomme eines Pferdes nicht auch seine Vorfahren sein kann.

Mit diesem Wissen sollten Sie Code Techniken spezifisch gerichtete azyklische Graphen gelten.