生成图的每种拓扑排序

Question

考虑这个表示图形的输入数组：

[
    {"id":1,"prev":["NaN"]},
    {"id":2,"prev":["NaN"]},
    {"id":3,"prev":[1]},
    {"id":4,"prev":[2]},
    {"id":5,"prev":[2]},
    {"id":6,"prev":[3,4]},
    {"id":7,"prev":[5,6]}
]

我的任务是找到对列表中的元素进行排序的每个可能选项。

元素的顺序取决于该元素是否有前一个元素。例如，没有。 7 永远是最后一个，因为它有 2 个前面的元素并且没有跟随者。

我尝试实现如下但没有成功：

var possibleSolutions = [];
recursiveCheck(tasks.slice(), tasks.length, []);

function recursiveCheck(array, noCalls, currentSolution) {
    var solution = currentSolution;
    array.forEach((task, index, object) => {
        if (task.prev.length <= 1 && isNaN(task.prev[0])) {
            var tmpTasks = array.slice();
            solution.push(task.id);
            tmpTasks.splice(index, 1);
            tmpTasks.forEach(el => {
                el.prev.forEach((prevEl, index, object) => {
                    if (prevEl == task.id) {
                        object.splice(index, 1)
                    }
                })
            })
            noCalls--;
            if (noCalls == 0) {
                possibleSolutions.push(solution)
                solution = [];
            } else {
                recursiveCheck(tmpTasks, noCalls, solution);
            }
        }
    });
}

这应该是输出：

[
    [1,2,3,4,5,6,7],
    [1,2,3,4,6,5,7],
    [1,2,3,5,4,6,7],
    [1,2,4,3,5,6,7],
    [1,2,4,3,6,5,7],
    [1,2,4,5,3,6,7],
    [1,2,5,3,4,6,7],
    [1,2,5,4,3,6,7],
    [1,3,2,4,5,6,7],
    [1,3,2,4,6,5,7],
    [1,3,2,5,4,6,7],
    [2,1,3,4,5,6,7],
    [2,1,3,4,6,5,7],
    [2,1,3,5,4,6,7],
    [2,1,4,3,5,6,7],
    [2,1,4,3,6,5,7],
    [2,1,4,5,3,6,7],
    [2,1,5,3,4,6,7],
    [2,1,5,4,3,6,7],
    [2,4,1,3,5,6,7],
    [2,4,1,3,6,5,7],
    [2,4,1,5,3,6,7],
    [2,4,5,1,3,6,7],
    [2,5,1,3,4,6,7],
    [2,5,1,4,3,6,7],
    [2,5,4,1,3,6,7]
]

再比如，数组不能像[1,3,6,...]那样排列，因为6前面有一个元素4，所以元素4必须在6之前。

Answer 1

让我们更抽象地讨论一下。

A directed graph 是我们真正作为输入的数据结构。我们有一组 V 的 vertices/nodes 和一组 E 的边。每条边都是一个有序对 (v1, v2)，其中 v1 和 v2 都是顶点，表示从 v1 到 v2 的箭头。在这里，我们使用“邻接列表”表示法来表示图形。

任务是找到topologically sort这张图的所有方法。

我们可以如下描述对图进行拓扑排序的方法：

如果我们想对空图（没有顶点的图）进行拓扑排序，这很简单：唯一的方法就是输出空排序[]。因此，对空图进行拓扑排序的所有方法列表将是 [[]].

现在，让我们考虑对非空图进行拓扑排序的问题。考虑一个序列 s，它是非空图 G 的一种拓扑排序。我们可以考虑 s 的第一个元素，我们称之为 x，以及所有其余元素的序列，我们称之为 s'.

我们知道x一定是G中的一个节点，并且我们知道x在G中不能有任何前驱。换句话说，不可能有节点 y 使得 (y, x) 是一条边。

我们也知道s'一定是G'_x的一种拓扑排序，也就是G但是有节点x（以及所有连接到它的边）已删除。

所以要得到G的所有拓扑排序，我们必须找到所有具有初始元素x和剩余元素s'的序列，使得x是一个G 的元素没有前导，s' 是 G'_x.

的拓扑排序

const remove_node = (g, x) => 
    g.flatMap((node) => node["id"] == x ? 
                        [] : 
                        {"id": node["id"], 
                         "prev": node["prev"].filter((id) => id != x)});

const topological_sorts = (g) => 
    g.length == 0 ?
    [[]] :
    g.filter((node) => node["prev"].length == 0)
     .map((node) => node["id"])
     .flatMap((id) => 
       topological_sorts(remove_node(g, id)).map((sorting) =>
         [id].concat(sorting)));

const remove_nan = (g) => g.map((node) => 
   ({ "id" : node.id, 
     "prev": node.prev.filter((predecessor) => 
       predecessor !== "NaN") } ));

const get_answer = (g) => topological_sorts(remove_nan(g));

在你的图表上调用 get_answer 将得出正确答案。

生成图的每种拓扑排序

Generate every topological sort of a graph

javascript

recursion

graph-theory

topological-sort