JavaScript 依赖列表

我有一个需要找出依赖关系的元素列表。

I have:

[{
  "a": ["b", "d"]
}, {
  "d": ["c", "e"]
}]

a取决于b and d, and d on c and e。有没有一种方法可以巧妙地构建依赖关系？输出应该（可能）是：

["b", "c", "e", "d", "a"]

/克里斯蒂安

假设您想要一个元素的递归依赖项列表，包括元素本身，以任何顺序：

“对于每个依赖项，将其依赖项添加到依赖项列表中”足够聪明吗？

function recursiveDependencies (dependencies, element){
  var output = [element];
  for(i=0; i<output.length(); i++){
    dependencies[output[i]].forEach(function(x){
      if(output.indexOf(x)<0){ //prevent duplicates
        output.push(x)
      }
    })
  }
  return output;
}

如果您希望元素本身位于末尾而不是开头，则可以使用以下命令修复该问题output.push(output.shift())

如果您希望依赖关系的顺序是每个元素都位于依赖它的元素之前，那么您必须定义如何处理循环依赖关系。处理这个问题的一种方法是检测循环依赖并失败。

如果每个依赖项最多被一个元素需要，那么您可以使用前一种算法：只需向后读取输出（或反转数组或使用unshift代替push（警告：性能下降））

依赖关系形成一个图，您正在寻找它的拓扑排序。一种（低效）方法是以深度优先顺序对节点进行排序，并在重新输入节点时重新插入它们。您可以使用开放堆栈来检测错误 - 如果子级从其父级重新输入，则存在循环依赖关系。

更好的解决方案是使用标准拓扑排序算法：虽然存在未排序的节点，但选择一个没有未解决的依赖关系的节点：

function recursiveDependencies (dependencies, root){
  var nodes={};
  var nodeCount=0;
  var ready=[];
  var output=[];

  // build the graph
  function add(element){
     nodeCount++;
     nodes[element]={needs:[], neededBy:[], name: element};
     if(dependencies[element]){
       dependencies[element].forEach(function(dependency){
         if(!nodes[dependency]) add(dependency);
         nodes[element].needs.push(nodes[dependency]);
         nodes[dependency].neededBy.push(nodes[element]);
       });
     }
     if(!nodes[element].needs.length) ready.push(nodes[element]);
  }

  if(root){
    add(root)
  } else {
     for (element in dependencies){
       if(!nodes[element]) add(element);
    }
  }


  //sort the graph
  while(ready.length){
    var dependency = ready.pop();
    output.push(dependency.name);
    dependency.neededBy.forEach(function(element){
      element.needs = element.needs.filter(function(x){return x!=dependency})
      if(!element.needs.length) ready.push(element)
    })
  }

  //error-check
  if(output.length != nodeCount){
    throw "circular dependency detected"
  }

  return output;
}

fiddle: http://jsfiddle.net/Xq5dz/4/ http://jsfiddle.net/Xq5dz/4/