C#:遍历对象图时避免无限递归

如果可以泛化循环(可以有任意数量的元素组成循环),则可以跟踪在循环中已经看到的对象 HashSet 如果访问对象时该对象已在集合中,则停止。或者在您访问对象时设置的对象上添加一个标志(但随后必须返回&完成后取消设置所有标志,图形一次只能由一个线程遍历)。

或者,如果循环将仅返回到父对象,则可以保留对父对象的引用,而不在引用回父对象的属性上进行循环。

真是巧合;这是本书的主题 my blog 这个星期一。有关更多详细信息,请参阅。在此之前,以下是一些代码,让您了解如何做到这一点:

static IEnumerable<T> Traversal<T>(
    T item,
    Func<T, IEnumerable<T>> children)
{
    var seen = new HashSet<T>();
    var stack = new Stack<T>();
    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 实例输出两次),因此通常需要在堆栈上推/弹出对象以检查真正的递归。上次实现“访问者”时,我保留了一个“深度”计数器,只启用了超过某个阈值的堆栈检查——这意味着 最 ++ -- ,但没有比这更贵的了。你可以看到我采取的方法 here .

我发表了一篇文章,用代码示例详细解释了如何通过递归反射进行对象遍历,以及如何检测和避免递归引用以防止堆栈溢出异常: https://doguarslan.wordpress.com/2016/10/03/object-graph-traversal-by-recursive-reflection/