带有承诺的图遍历

Question

我想知道如何使用 promises 编写图遍历算法（我正在使用 JavaScript/Bluebird）。每个节点的定义都在数据库中，获取每个节点是异步的。

让我们考虑广度优先搜索，其中给定根节点，每个节点都有对其子节点的引用。我们需要获取根节点的子节点并将它们排入 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();
    })
}

带有承诺的图遍历

Graph-traversal with promises

javascript

node.js

promise

bluebird