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

伪代码:

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

基本思想是保存一个列表,其中列出了我们在到达当前节点的过程中已经看到的所有节点;如果我们回到一个我们已经经历过的节点,那么你知道我们已经形成了一个循环(我们应该跳过这个值,或者做任何需要做的事情)

维护指向树根的所有元素的堆栈。

(对于系谱数据,树中的“子”节点可能是“父”节点的生物父节点。)

这听起来像是一个最终可以应用面试琐碎问题的案例:仅使用O(1)内存在链表中找到一个循环。

在这个例子中,我用更简单的“drop markers”方法替换了“half speed”方法。

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

检测这种情况的一种非常简单的方法是检查约束本身:

不可能发生的事情是,一匹马以父亲、祖父或曾祖父的身份出现。

每当在树中插入节点时,将树遍历到根,以确保马不作为任何类型的父对象存在。

为了加快速度,您可以将哈希表关联到每个节点,在其中缓存此类查找的答案。这样,下次在该节点下插入马时,就不必搜索整个路径。

如果跟踪节点而不是马匹,则哈希表解决方案应该可以工作。只要确保每次读取新的马时都创建了一个新节点,即使该值/马与前一个节点的值/马相同。

directed acyclic graph

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