反应深度优先搜索

本文关键字：深度优先搜索 | 更新日期: 2023-09-27 18:18:36

我正在尝试开发一个响应式DFS实现，它可以产生不同的节点，而不需要遍历不必要的路径。树可能包含重复/相等的节点。如果一个节点已经被遍历，那么它的所有子节点也都被遍历了，因此如果我们再次遇到一个节点，我们可以停止扩展遍历。

class Traversal {
  //exposed method with understandable signature
  public IObservable<Node> DepthFirst(Node root) {
    return DepthFirstRecursive(root, new List<Node>(), new SomeStatefulHelper());
  }
  //hidden method with accumulator for cutting
  private IObservable<Node> DepthFirstRecursive(Node root, List<Node> accuFilter, SomeHelper helper) {
    return root.GetChildren().AsObservable()
      //here we cut traversal:
      .Where(n => !accuFilter.Contains(n))
      //cannot do SelectMany, because we want sequential processing:
      .Select(n => DepthFirstRecursive(n, accuFilter, helper)).Concat()
      .Concat(Observable.Return(root))
      //adding results to accumulator
      .Do(accuFilter.Add)
  }
}
class Node : IEquatable<Node> {
  public IEnumerable<Node> GetChildren(SomeHelper helper) {
    //produce child nodes
  }
  ...
}

累加器不美观。它基本上是通过优雅的响应式实现编织的副作用。我如何使用Rx摆脱它? Observable.Distinct()不会切割它(双关语)，因为它只能在链的最后(.Do所在的地方)操作。

此外，有了帮助器，我在.Where中的=>上得到了一个"隐式捕获的闭包:助手"警告。我看不出这个警告有什么意义。是吗?我怎样才能摆脱它?

反应深度优先搜索

我认为RX不适合这里的工作。

另外，您应该使用HashSet来跟踪访问的节点。
List.Contains()遍历所有元素，因此您将引入O(n^2)行为。

最简单的方法是使用Enumerable.SelectMany()

不需要依赖额外的类来实现GetChildren()，您可以简单地使用委托Func<T, IEnumerable<T>> getChildren来指定如何获得所讨论的节点类型的子节点。

我是这样做的:

    public static IEnumerable<T> DepthFirst<T>(T node, 
                                               Func<T, IEnumerable<T>> getChildren, 
                                               HashSet<T> visitedNodes)
    {
        return getChildren(node)
              .Where(visitedNodes.Add)
              .SelectMany(child => DepthFirst(child, getChildren, visitedNodes))
              .Concat(new[] { node });
    }
    public static IEnumerable<T> DepthFirst<T>(T root, 
                                               Func<T, IEnumerable<T>> getChildren) 
    {
        return DepthFirst(root, getChildren, new HashSet<T> {root});
    }
相关文章：