如何按相互依赖的顺序对数组进行排序

Question

我知道标题很难懂。

下面我用简单的代码来简单说明一下

var objA = {
    id: 1
}
var objB = {
    id: 2,
    children: [1,3] //<== this is ID of objA and objC
}
var objC = {
    id: 3,
    children: [1] //<== this is ID of objA
}

function myFunction(){
    const list = [objA, objB, objC];
    // Do something to sort to [objA, objC, objB]
    var listSorted = ...;
    for(var item in listSorted){
        //Do something else
    }
}

上面的demo代码中，objA是独立的，所以应该先运行，objB依赖于objA和objC 所以它应该是运行在 objA 和 objC 之后，依此类推。所以排序后list，应该是[objA, objC, objB]

Answer 1

试试这个：

    function canRun(obj, readyIds) {
        // Without childs... can run
        if (!obj.children || obj.children.lenght === 0)
            return true;

        // If some req is not added yet... can't run
        for (let i = 0; i < obj.children.length; i++) {
            if (!readyIds[obj.children[i]])
                return false;
        }

        return true;
    }

    function getSortedList(list) {
        let readyIds = [];
        let listSorted = [];
        let someChanged = true;

        while (list.length > 0 && someChanged) {
            someChanged = false;

            for (let i = list.length - 1; i >= 0; i--) {
                var item = list[i];

                if (canRun(item, readyIds)) {
                    list.splice(i, 1);
                    listSorted.push(item);
                    readyIds[item.id] = true;
                    someChanged = true;
                }
            }
        }

        return listSorted;
    }

canRun 检查项目何时可以执行：它没有依赖项或之前已添加所有依赖项。

为了对项目进行排序，我们迭代列表删除可以运行的项目并添加到 listSorted 中。我们需要稍后做，因为在每个 for 中我们只能添加没有依赖项的项目。 someChanged 是为了安全，以防某些项目无法执行，以防止无限期。在正常情况下，列表变为空并且 listSorted 具有所有项目。如果某些项目不能执行，列表有这些项目和listSorted，可以执行的项目。

测试代码：

    var objA = {
        id: 1
    }
    var objB = {
        id: 2,
        children: [1, 3] //<== this is ID of objA and objC
    }
    var objC = {
        id: 3,
        children: [1] //<== this is ID of objA
    }

    let list = [objA, objB, objC];
    let listSorted = getSortedList(list);

如何按相互依赖的顺序对数组进行排序

How to sort Array by order of dependent each other

javascript

algorithm