按照依赖列表对对象数组进行排序？

Question

我需要对由名称和依赖项列表（由名称组成）组成的对象数组进行排序。

这个数组的一个例子是：

[
  { name: 'a', requires: ['b', 'c'] },
  { name: 'b', requires: ['c'] },
  { name: 'c', requires: [] },
]

我希望这个数组能够被排序，使得需要特定依赖项的项目会在其所需的依赖项之后。
实际上，该数组可能包含更多项目，如果存在循环依赖关系，则排序函数抛出错误也可以。

示例输出：

[
  { name: 'c', requires: [] }, // first, no dependencies, and required by both the others
  { name: 'b', requires: ['c'] }, // second, because it needs `c` first
  { name: 'a', requires: ['b', 'c'] }, // last, because requires both the others
]

什么是最简洁的方法实现它？

- Fez Vrasta

---

请展示一下你尝试过的内容。 - Peter B

我其实不知道从哪里开始@PeterB，我的第一次尝试是使用Array.sort，但它并不适合这项工作。 - Fez Vrasta

@VigneshMurugan 这不是一个要求，只需要满足依赖关系即可。 - Fez Vrasta

FYI，这不仅仅是一个排序问题，它主要是一个连通图问题。 - Peter B

Answer 1

您可以尝试以下方法（更改测试用例以支持更多可能的组合）

var arr = [
  { name: 'd', requires: ['a', 'c'] },
  { name: 'a', requires: ['b', 'c'] },
  { name: 'b', requires: ['c'] },
  { name: 'e', requires: ['d'] },
  { name: 'c', requires: [] },
];

var map = {}; // Creates key value pair of name and object
var result = []; // the result array
var visited = {}; // takes a note of the traversed dependency

arr.forEach(function(obj){ // build the map
  map[obj.name]  = obj;
});

arr.forEach(function(obj){ // Traverse array
  if(!visited[obj.name]) { // check for visited object
    sort_util(obj);
  }
});

// On visiting object, check for its dependencies and visit them recursively 
function sort_util(obj){
    visited[obj.name] = true;
    obj.requires.forEach(function(dep){
        if(!visited[dep]) {
           sort_util(map[dep]);
        } 
    });
    result.push(obj);
}

console.log(result);

- Nikhil Aggarwal

---

这个解决方案只有在正确的顺序给出时才能（如果有的话）起作用。对于其他给定的顺序，依赖关系不会被尊重。 - Nina Scholz

Answer 2

更新：感谢Nina Scholz，我更新了代码，以便sort可以工作。

这可能会完成任务。 其背后的想法是使用sort并检查元素a是否在元素b的要求中。如果是这样，我们可以假设a应该在b之前。 但我不能百分之百确定，我只是根据您的示例和@nikhilagw的示例进行了检查。我可能忘记了某些内容。如果它起作用，请告诉我！

对于每个元素，我还继承所有依赖项。

const list = [
{ name: 'b', requires: ['c'] },
{ name: 'e', requires: ['d'] },
{ name: 'd', requires: ['a', 'c'] },
{ name: 'c', requires: [] },  
{ name: 'a', requires: ['b', 'c'] }, 
];

// indexed by name
const mapped = list.reduce((mem, i) => {
  mem[i.name] = i;
  return mem;
}, {});

// inherit all dependencies for a given name
const inherited = i => {
  return mapped[i].requires.reduce((mem, i) => {
  return [ ...mem, i, ...inherited(i) ];
  }, []);
}

// order ... 
const ordered = list.sort((a, b) => {
  return !!~inherited(b.name).indexOf(a.name) ? -1 : 1;
})

console.log(ordered);

- Luke

---

只有在正确的顺序下，此解决方案才能（如果有的话）起作用。对于其他给定的顺序，依赖关系将不被尊重。 - Nina Scholz

但是这些项目不在正确的顺序中，你觉得它为什么不能工作？你能解释一下吗？ - Luke

实际上我得到的是 a d b e c，应该是 c b a d e，即使反转，结果也不匹配。排序的问题在于，你只检查两个元素及其关系，但它不尊重之前需要的元素，因为某些元素指向一个项目，同时指向项目的前任。 - Nina Scholz

你说得对。我会修复它，以便所有的依赖项都能被继承。那应该解决了那个问题。 - Luke

@NinaScholz，您能再检查一下吗？我仍然喜欢sort和更多的函数式方法。 - Luke

Answer 3

几年过去了，我终于找到了这个超级简短的解决方案，是一个朋友与我分享的，我并不希望获得任何荣誉。

elements.sort((a, b) =>
  a.requires.includes(b.name) ? 1 : b.requires.includes(a.name) ? -1 : 0
);

- Fez Vrasta

Answer 4

这个提案查找先前的元素并检查实际元素是否按要求排序。

如果找到了所有要求，则将对象拼接到索引处。

function order(array) {
    var i = 0,
        j,
        temp;

    while (i < array.length) {
        temp = array.slice(0, i);
        for (j = i; j < array.length; j++) {
            if (array[j].requires.every(n => temp.some(({ name }) => n === name))) {
                array.splice(i++, 0, array.splice(j, 1)[0]);
                break;
            }
        }
    }
    return array;
}

var array = [{ name: 'd', requires: ['a', 'c'] }, { name: 'a', requires: ['b', 'c'] }, { name: 'b', requires: ['c'] }, { name: 'e', requires: ['d'] }, { name: 'c', requires: [] }];

console.log(order(array));

.as-console-wrapper { max-height: 100% !important; top: 0; }

- Nina Scholz

Answer 5

你的数据可以通过图表来表示。因此，你可以使用拓扑排序来解决这个问题。

- TLamp