algorithm - 稳定拓扑排序

Question

假设我有一个图表，其中节点存储在排序列表中。我现在想对这个图进行拓扑排序，同时在拓扑顺序未定义的情况下保持原始顺序。有什么好的算法吗？

Answer 1

一种可能性是计算字典序最小的拓扑顺序。该算法将维护一个优先级队列，其中包含有效入度(在尚未处理的节点之上)为零的节点。重复使标签最少的节点出列，将其附加到订单中，减少其后继节点的有效入度，将入度为零的节点入队。这会在 btilly 的示例中产生 1234567890，但通常不会最小化反转。

我喜欢这个算法的特性是输出有一个清晰的定义，显然只满足一个订单，而且，每当有反转(节点 x 出现在节点 y 之后，即使 x < y)，x 的最大依赖性更大比 y 最大的依赖性，这是反转 x 和 y 的各种“借口”。一个推论是，在没有约束的情况下，lex 最小顺序是排序顺序。