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

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

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