6

我正在递归加载马家谱数据。对于一些错误的数据集，我的递归永远不会停止......那是因为数据中有循环。

如何检测这些周期以停止重复？

我想到在重复维护一个包含所有“访问”马的哈希表时。但这会发现一些误报，因为一匹马可以在一棵树上出现两次。

不可能发生的是，一匹马以自己的父亲或祖父或曾祖父的身份出现。

4

6 回答 6

6

伪代码：

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

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

于 2009-03-07T03:23:10.053 回答
2

维护一个由所有元素组成的堆栈，直到树的根。

每次沿着树前进时，扫描堆栈中的子元素。如果您找到匹配项，那么您已经发现了一个循环并且应该跳过那个孩子。否则，将孩子推入堆栈并继续。每当您回溯树时，将一个元素从堆栈中弹出并丢弃。

（在家谱数据的情况下，树中的“子”节点可能是“父”节点的生物学父节点。）

于 2009-03-07T03:21:32.787 回答
2

这听起来像是您最终可以应用面试琐事问题的情况：仅使用 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);
    }
}
于 2009-03-15T04:00:05.370 回答
1

检测这一点的一个非常简单的方法是检查该约束本身：

不可能发生的是，一匹马以自己的父亲或祖父或曾祖父的身份出现。

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

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

于 2009-03-07T03:22:58.197 回答
0

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

于 2009-03-07T03:23:59.490 回答
0

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

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

于 2009-03-07T03:26:03.697 回答