C＃：遍历对象图时避免无限递归
我有一个对象图，其中每个子对象包含一个引用回其父对象的属性。 是否有任何好的策略忽略父引用以避免无限递归？ 我考虑过为这些属性添加特殊的[Parent]属性或使用特殊的命名约定，但也许有更好的方法。
如果循环可以被推广（你可以有任意数量的元素组成循环），你可以跟踪你已经在HashSet看到过的对象，并在访问它时对象已经在集合中停止。 或者在您访问它时设置的对象上添加一个标志（但是当您完成时必须返回并取消设置所有标志，并且图形一次只能由一个线程遍历）。
或者，如果循环只返回到父级，则可以保留对父级的引用，而不是循环引用它的属性。
为简单起见，如果您知道父引用将具有某个名称，则您可能无法循环该属性:)
多么巧合; 这是我星期一的博客主题。 有关更多详细信息，请参阅 在此之前，这里有一些代码可以让您了解如何执行此操作：
static IEnumerable Traversal ( T item, Func> children) { var seen = new HashSet (); var stack = new Stack (); seen.Add(item); stack.Push(item); yield return item; while(stack.Count > 0) { T current = stack.Pop(); foreach(T newItem in children(current)) { if (!seen.Contains(newItem)) { seen.Add(newItem); stack.Push(newItem); yield return newItem; } } } }
该方法有两个方面：一个项目，以及一个产生与项目相邻的所有东西的集合的关系。 它产生深度优先遍历项目的邻接关系的传递和反身闭包 。 假设分支因子不受限制，假设图中项的数量为n，最大深度为1 <= d <= n。 该算法使用显式堆栈而不是递归，因为（1）递归在这种情况下将应该是O（n）算法转换为O（nd），然后在O（n）和O（n ^ 2）之间， （2）如果d超过几百个节点，则过多的递归会使堆栈爆炸。
注意，该算法的峰值存储器使用当然是O（n + d）= O（n）。
所以，例如：
foreach(Node node in Traversal(myGraph.Root, n => n.Children)) Console.WriteLine(node.Name);
合理？
如果您正在进行图遍历，则可以在每个节点上使用“已访问”标记。 这可以确保您不会重新访问节点并可能陷入无限循环。 我相信这是执行图遍历的标准方法。
我不确定你在这里尝试做什么，但是当你正在进行深度优先搜索的广度优先搜索时，你可以只维护所有先前访问过的节点的哈希表。
这是一个常见问题，但最佳方法取决于方案。 另一个问题是，在许多情况下， 访问同一对象两次并不是一个问题 – 这并不意味着递归 – 例如，考虑树：
A => B => C => D => C
这可能是有效的（想想XmlSerializer ，它只会将C实例写出两次），因此通常需要在堆栈上推送/弹出对象以检查真正的递归。 我最后一次实现“访问者”时，我保留了一个“深度”计数器，并且只启用了超过某个阈值的堆栈检查 – 这意味着大多数树只是最终做了一些++ / -- ，但没有更昂贵。 你可以看到我在这里采取的方法。
我发布了一篇post，详细解释了代码示例如何通过递归reflection进行对象遍历，还检测并避免递归引用以防止堆栈溢出exception： https ： //doguarslan.wordpress.com/2016/10/03/object -图遍历-由递归reflection/
在该示例中，我使用递归reflection进行了深度优先遍历，并且我为参考类型维护了受访节点的HashSet。 有一点需要注意的是使用自定义相等比较器初始化HashSet，它使用对象引用进行哈希计算，基本上是由基础对象类本身实现的GetHashCode（）方法，而不是任何重载版本的GetHashCode（），因为如果类型您遍历重载GetHashCode方法的属性，您可能会检测到错误的哈希冲突，并认为您检测到一个递归引用，实际上可能是GetHashCode的重载版本通过一些启发式方法生成相同的哈希值并混淆了HashSet，所有您需要的detect是检查对象树中任何位置指向内存中相同位置的父子。