在深度优先搜索期间检测谱系图中的循环

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

您正在处理有向无环图，而不是树。 不应该有任何循环，因为马的后代不可能也是它的祖先。

知道这一点后，您应该应用特定于有向无环图的代码技术。