Javascript：對涉及I/O的定向樹的DFS遍歷

Question

給定一個定向樹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操作。它不會返回任何內容，並且需要一個回調參數來處理返回的子項。

一個修改後的代碼的解決方案（這是WRONG）可以是這樣的：

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。更糟糕的是，返回語句與匿名回調函數相關聯，並在封閉函數完成運行後執行。

很明顯，需要某種流量控制機制。什麼是這個問題的簡單而優雅的解決方案？

更新：我接受了塞巴斯蒂安的答案，因爲它解決了遞歸問題，這就是我提出問題的方式。我還發布了一個使用async's庫whilst循環的答案，這是我最終使用的。 Sebastien非常友好地以這兩種方法爲基準here。（擾流板：性能相同）

Answer 1

第一，我認爲你必須調用findGoodPath（兒童[I]，深度+ 1），如果你想深度等於PATH_SIZE。

那麼，你確實有關閉的問題，你的異步調用總是與一個節點實例連接，而不是你想要的那個。

你可以這樣做，可能是210

方式一：

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)); 
} 

Answer 2

我不是100％在現在的重點，但我幾乎可以肯定Async.js seriestasks是您正確的解決方案（如果沒有seriestasks我敢打賭，還有另外一個控制流入Async.js，會做的伎倆。

Answer 3

OK，所以有幾種方法可以實現異步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; 
} 

注意：我救了整個路徑的每一個節點，這不是必須的，你可以保存深度並保持當前路徑的數組，雖然有點麻煩。

然後我用了async庫這個功能轉化爲一個異步之一，異步的whilst()取代標準while()功能：

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); 
     } 
    ); 
} 

不漂亮的一個，但它的可讀性和它的工作。