查找拓扑排序的数字顺序

Question

我有一个无环图，每个顶点都有数字标签我想为这个图找到 Topological Sort；然而，一个图可能包含多个拓扑顺序，但我想找到顶点编号具有数字顺序的特定顺序，请参见下图以获取更多解释

正如你在上图中看到的，这张图包含了几个拓扑顺序
4 5 6 1 2 3
1 4 2 5 6 3
1 2 4 5 3 6
1 2 3 4 5 6
......
但是我需要这个顺序 1 2 3 4 5 6 我想知道我应该如何更改拓扑排序算法才能找到这个特定顺序

这是另一个例子：

在示例图中，这两个顺序为真
2 1 0
但是当我使用第一个答案排序函数时，它会交换 2 和 0，最终结果将是 0 1 2，这是一个错误的答案

Answer 1

如果您对 拓扑排序算法 的输出再执行一次排序，并在排序时使用以下比较函数，效果会更好：

//Suppose we have a method which returns true if an edge exists between two nodes.
//returns false otherwise.
edgeExists(node1,node2) ==true  // node1->node2

//The compare function
//consider node.value as vertex number.
bool compare(node1, node2){
    if(node1.value > node2.value && !edgeExists(node1,node2))
         return false;

    return true;
}

下面是@Gene建议的比较方法的优化：

bool compare(node1, node2){
      return (edgeExists(node1,node2) || node1.value < node2.value) ;
}

需要考虑的一个非常重要的事情是，只有当传递的顶点在提供的拓扑顺序中是连续的时，此比较方法才能正确工作。

所以我们必须选择一个总是只比较连续元素的排序算法。是的，冒泡排序!!!

请注意，您可以直接使用冒泡排序来获取顺序，但是如果您已经有了拓扑排序的输出并且想要获得更有序的排序，则应该使用上述方法。

查找拓扑排序的数字顺序

Find numeric order of topological sort

algorithm

sorting

topological-sort