检测周期在一家谱图在一个深度的第一个搜索

StackOverflow https://stackoverflow.com/questions/621229

题

我载入马的家谱数据。对一些错误的数据集递归我永远不会停止...这是因为存在周期中的数据。

我怎么可以测那些周期，以停止的经常性?

我认为，同时经常性的维持hashTable与所有"拜访"马。但是，会发现某些误判，因为一匹马可以两次在一棵树上。

什么不可能发生的是一匹马的出现作为一个父亲或祖父或曾祖父的本身。

有帮助吗？

解决方案

伪码：

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)存储器。

在这种情况下你的"联的列表"是序列的元素一一列举。使用两个统计员，运行一个一半速度，并且如果一个曾经入运行缓慢的一个然后你有一个循环。这也是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);
    }
}

一个非常简单的方法以检测此，是通过检查这一制约因素本身：

什么不能发生的是，一匹马有出现作为一个父亲或祖父或greatgrandfather的本身。

只要你插入一个节点在你的树，穿越树根，以确保这匹马不存在作为任何种类的父母。

加速这个了，你可以联系hashtable每个节点，在这里您缓回答这样一个查找。然后你不需要搜索整个路径下一次插入一个马下的节点。

你希表解决方案应工作，如果你跟踪的节点，而不是马。只是确保每次你读一个新的马创建一个新的节点，即使该价值/马同以前的节点的数值/马。

你处理一个 针对环图, 不一棵树。不应有任何周期，作为一个马的后代也不能以其祖先。

知道了这一点，则应适用于代码技术的具体定向环的图表。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top