深度优先搜索过程中发现的族谱图周期 [英] Detect cycles in a genealogy graph during a Depth-first search

问题描述

我加载马家谱数据递归。 对于一些错误数据组我的递归从不停止...，这是因为在数据有循环。

I'm loading horse genealogical data recursively. For some wrong sets of data my recursion never stops... and that is because in the data there are cycles.

我如何检测这些周期停止递归？

我的吼声，而递归十个分量与所有哈希表的访问的马。 但是，这会发现一些假阳性，因为马可两次在一棵树上。

I thougth of while recursing mantain a hashTable with all "visited" horses. But that will find some false positives, because a horse CAN be twice in a tree.

什么不能happend是，一匹马出现​​作为一个父亲本身或祖父或曾祖父。

What cannot happend is that a horse appear as a father or grandfather or greatgrandfather of ITSELF.

推荐答案

伪code：

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

其基本思想是让所有我们已经看到在我们一路下滑到当前节点的节点列表;如果是回到那个我们已经经历了一个节点，那么你知道，我们已经形成了一个循环（我们应该跳过值，或做任何需要做的事情）

The basic idea is to keep a list of all of the nodes that we've already seen on our way down to the current node; if was get back to a node that we already went through, then you know that we've formed a cycle (and we should skip the value, or do whatever needs to be done)

这篇关于深度优先搜索过程中发现的族谱图周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！