javascript - 根据子项重新排序数组

Question

我想获得一个有序数组，以便能够首先执行子级，然后执行所有父级。

这是一个例子:

var p1=[c1,c2,c3] // c1,c2,c3 are children
var p2=[c4,c5,c6]
var c1=[c2,p2] // but c1 can depend on parent

所以结果应该是:

var result=[c2,c6,c4,c5,c2,c3,p2,c1,p1]

另一个示例可能是重新排序 npm 依赖项，首先安装所有子项，然后安装剩余的父项，以避免由于缺少子项安装而出现错误。

预先感谢您的帮助。

Answer 1

这称为topological sorting 。这是卡恩算法的简单实现(请参阅链接):

var graph = {
    p1: ['c1', 'c2', 'c3'],
    p2: ['c4', 'c5', 'c6'],
    c1: ['c2', 'p2']
};

var terminals = {},
    sorted = [];

Object.keys(graph).forEach(n =>
    graph[n].forEach(k =>
        k in graph ? '' : terminals[k] = 1));

terminals = Object.keys(terminals);

while (terminals.length !== 0) {
    var t = terminals.shift();
    sorted.push(t);
    Object.keys(graph).forEach(n => {
        graph[n] = graph[n].filter(x => x != t);
        if (graph[n].length === 0) {
            terminals.push(n);
            delete graph[n];
        }
    });
}

console.log(sorted)