javascript - 带 promise 的图遍历

Question

我想知道如何使用 Promise 编写图形遍历算法(我使用的是 JavaScript/Bluebird)。每个 Node 的定义都在数据库中，获取每个 Node 是异步的。

让我们考虑一个广度优先搜索，其中我们得到根 Node ，并且每个 Node 都有对其子 Node 的引用。我们需要获取根 Node 的子 Node 并将它们排入 nodesToVisit 队列，依此类推。

考虑以下代码:

var Promise = require('bluebird');

var nodesToVisit = [{id:1, children:[2,3]}]; // 1 is the root

Promise.each(nodesToVisit, val => {
    console.log(val.id);
    if(val.children) {
       val.children.forEach(child => {
         var getChildFromDatabasePromise = myDatabase.get(child); 
         nodesToVisit.push(getChildFromDatabasePromise);
       });
    }
});

这不起作用，因为 Promise.each 将在将 getChildFromDatabasePromise 推送到它之前完成。

我想问题的核心是如何使用promise来制作动态的while循环？

Answer 1

将代码包装在函数中并递归调用它怎么样？

var nodesToVisit = [{id:1, children:[2,3]}]; // 1 is the root

visitNextBatch();

function visitNextBatch() {
    var copyOfNodes = nodesToVisit;
    nodesToVisit = [];
    Promise.each(copyOfNodes, val => {
        console.log(val.id);
        if(val.children) {
            val.children.forEach(child => {
            var getChildFromDatabasePromise = myDatabase.get(child); 
            nodesToVisit.push(getChildFromDatabasePromise);
           });
        }
    }).then(function() {
        visitNextBatch();
    })
}