4

给定一个每个节点具有可变数量的子节点的有向树 T，我想找到一条从根开始的“好”节点的 PATH_SIZE 大小的路径。

每个节点都有一个isGood()方法和一个getChildren()按预期工作的方法。

一个简单的 DFS 递归解决方案如下所示：（如果我错了，请纠正我）

function findGoodPath(node, depth){
    if(!node.isGood()){
        return null;
    } else if (depth==PATH_SIZE){
        return [node];
    }
    var children = node.getChildren();
    for (var i=0; i<children.length; i++){
        var result = findGoodPath(children[i], depth+1);
        if (result){
            return result.concat([node]);
        }
    }
    return null;
}

findGoodPath(root, 1)如果存在，调用应该找到结果。

现在问题来了：getChildren()节点对象的方法实际上是一个在幕后进行 I/O 的异步方法。它什么也不返回，并期望一个回调参数来处理返回的孩子。

修改后的代码解决方案（错误）可能如下所示：

function findGoodPath(node, depth){
    if(!node.isGood()){
        return null;
    } else if (depth==PATH_SIZE){
        return [node];
    }
    node.getChildren(function(children){
        for (var i=0; i<children.length; i++){
            var result = findGoodPath(children[i], depth+1);
            if (result){
                return result.concat([node]);
            }
        }
    });
}

这个解决方案行不通：单个节点的子节点的所有 getChildren 方法将被立即调用，因此它实际上会执行 BFS。更糟糕的是，return 语句与匿名回调函数相关联，并将在封闭函数完成运行后执行。

很明显，需要某种流量控制机制。这个问题的简单而优雅的解决方案是什么？

更新：我接受了 Sebastien 的回答，因为它通过递归解决了这个问题，这就是我提出问题的方式。我还发布了一个使用异步库while循环的答案，这就是我最终使用的。Sebastien 非常友好地在这里对这两种方法进行了基准测试。 （剧透：性能相同）

4

3 回答 3

1

首先，如果您希望深度等于 PATH_SIZE，我认为您必须调用 findGoodPath(children[i], depth + 1)。

那么，你确实有关闭的问题。通过您的异步调用，您总是与一个节点实例连接，而这不是您想要的。

您可以这样做的一种方法是：

node.getChildren((function(_node) {
  return function(children){
    for (var i=0; i<children.length; i++){
      var result = findGoodPath(children[i], depth);
        if (result){
          return result.concat([_node]);
        }
      }
    });
})(node));

但我认为这只是问题的一部分，因为您将同步功能与异步功能混合在一起。该行：

var result = findGoodPath(children[i], depth)

编写为同步调用，而 findGoodPath 是异步函数，因此也必须使用回调编写！

希望能帮助到你

ps：有一个jsfiddle会有所帮助......

更新：试一试。由于我无法测试，它不起作用，但它就是这个想法。我不知道您是否需要在第二个 findGoodPath 调用中创建另一个范围，就像在 getChildren 调用中一样

function findGoodPath(node, depth, callback){
  if(!node.isGood()){
    return callback(null);
  } else if (depth==PATH_SIZE){
    return callback([node]);
  }
  node.getChildren((function(_node, _callback) {

    return function(children){
      var node = _node, callback = _callback;

      for (var i=0; i<children.length; i++){
        findGoodPath(children[i], depth, function(result) {
          if (result){
            return callback(result.concat([node]));
          }
        });
      }
    });
  })(node, callback));
}
于 2013-08-18T20:09:18.207 回答
0

我现在不是 100% 专注，但我几乎可以肯定Async.js seriestasks是适合您的解决方案（如果不是 seriestasks，我愿意打赌 Async.js 中还有另一个控制流可以解决问题。

于 2013-08-18T17:47:50.903 回答
0

好的，所以有几种方法可以实现异步 DFS 遍历。由于异步递归倾向于变得有些丑陋，我决定摆脱递归。

我首先使用 while 循环而不是递归重新实现了函数的同步版本：

function findGoodPathLoop(root){
    var nodesToVisit = [{data: root, path:[]}];
    while (nodesToVisit.length>0){
        var currentNode = nodesToVisit.pop();
        if (currentNode.data.isGood()){
            var newPath = currentNode.path.concat(currentNode.data);
            if (newPath.length==PATH_SIZE){
                return newPath;
            } else {
                var childrenNodes = currentNode.data.getChildren().map(function(child){
                    return {data: child, path: newPath};
                });
                nodesToVisit = nodesToVisit.concat(childrenNodes);
            }
        }
    }
    return null;
}

注意：我保存了每个节点的整个路径，这不是必需的，您可以只保存深度并维护当前路径的数组，尽管它有点混乱。

然后我使用异步库将此函数转换为异步函数，用while()异步替换标准函数whilst()：

function findGoodPathAsync(root, pathCallback){
    var result = null;
    var nodesToVisit = [{data: root, path:[]}];
    async.whilst(
        function(){
            return nodesToVisit.length>0 && result==null ;
        },
        function(next) {
            var currentNode = nodesToVisit.pop();
            if (currentNode.data.isGood()){
                var newPath = currentNode.path.concat(currentNode);
                if(newPath.length==PATH_SIZE){
                    result = newPath;
                    next();
                } else {
                    currentNode.data.getChildren(function(children){
                        var childrenNodes = children.map(function(child){
                            return {data: child, path: newPath};
                        });
                        nodesToVisit = nodesToVisit.concat(childrenNodes);
                        next();
                    });
                }
            } else {
                next();
            }
        },
        function(err) {
            //error first style callback
            pathCallback(err, result);
        }
    );
}

不是一个漂亮的，但它是可读的并且它可以完成工作。

于 2013-08-18T23:31:49.280 回答