Обнаружение циклов в графе генеалогии во время поиска в глубину

Question

Я загружаю конские генеалогические данные рекурсивно. Для некоторых неправильных наборов данных моя рекурсия никогда не останавливается ... и это потому, что в данных есть циклы.

Как определить, чтобы эти циклы перестали повторяться?

Я думал о том, чтобы при повторном обращении поддерживать хэш-таблицу со всеми посещенными " лошади. Но это найдет некоторые ложные срабатывания, потому что лошадь МОЖЕТ быть дважды на дереве.

Чего не может случиться, так это того, что лошадь предстает отцом, дедом или прадедом САМОГО.

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

Это звучит как случай, когда вы наконец можете применить этот вопрос о пустяках интервью: найдите цикл в связанном списке, используя только O (1) памяти.

В этом случае ваш " связанный список " это последовательность элементов, которую вы перечисляете. Используйте два перечислителя, запустите один на половинной скорости, и если быстрый когда-нибудь попадет в медленный, у вас будет цикл. Это также будет время O (n) вместо времени O (n ^ 2), необходимого для проверки «видимого» списка. Недостатком является то, что вы узнаете о цикле только после того, как некоторые узлы были обработаны несколько раз.

В этом примере я заменил метод «половинной скорости» более простым для записи методом «маркеров сброса».

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

Очень простой способ определить это, проверив само это ограничение:

  

Чего не может случиться, так это того, что лошадь предстает отцом, дедом или прапрадедом САМ.

Всякий раз, когда вы вставляете узел в свое дерево, обходите дерево до корня, чтобы убедиться, что лошадь не существует в качестве какого-либо родителя.

Чтобы ускорить это, вы можете связать хеш-таблицу с каждым узлом, где вы кешируете ответ такого поиска. Тогда вам не придется искать весь путь в следующий раз, когда вы вставите лошадь под этим узлом.

Answer 5

Ваше решение для хеш-таблицы должно работать, если вы отслеживаете узлы вместо лошадей. Просто убедитесь, что каждый раз, когда вы читаете новую лошадь, вы создаете новый узел, даже если значение / лошадь совпадает со значением / лошадью предыдущего узла.

Answer 6

Вы имеете дело с направленным ациклическим графом , а не деревом. Не должно быть никаких циклов, так как потомок лошади не может быть и ее предком.

Зная это, вы должны применять методы кода, специфичные для направленных ациклических графов.