递归枚举图

Question

我有以下(其混凝土):

public interface IDirectory
{
   IEnumerable<IDirectory> Directories{get;}
}

我建一个图形ñ深目录.现在我想枚举从根目录开始并递归到终端/最深目录的目录,我必须按顺序进行,IE在返回它的父节点之前永远不会返回目录.我确信有一个优雅的解决方案,但它在我的时区已经很晚了,我的灰质已经累了,所以任何指针都非常赞赏.

Answer 1

另外两个解决方案是这个问题的典型递归解决方案,适用于没有周期的浅图.如果你有一个带有周期的深图,那么它们就不会有效.你最好用这样的东西:

public static IEnumerable<T> DepthFirstTraversal<T>(
    T root, 
    Func<T, IEnumerable<T>> children)
{
    var set = new HashSet<T>();
    var stack = new Stack<T>();
    stack.Push(root);
    while(stack.Count != 0)
    {
        T current = stack.Pop();
        if (set.Contains(current)) continue;
        yield return current;
        set.Add(current);
        foreach(var child in children(current))
            stack.Push(child);
    }
}

然后用它来调用它

foreach(var d in DepthFirstTraversal(root, x=>x.Directories))
   ...

该集合跟踪已经访问的节点,因此占用O(n)空间.没有递归,因此它在堆栈空间中是O(1).

如果您知道没有循环,则可以消除该设置并节省该成本.