稳定的拓扑排序 [英] Stable topological sort

问题描述

让说，我有其中的节点存储在一个排序列表的图。我现在想拓扑排序这个图，同时保持那里的拓扑顺序是不确定的原始顺序。 是否有任何好的算法呢？

Let say I have a graph where the nodes is stored in a sorted list. I now want to topological sort this graph while keeping the original order where the topological order is undefined. Are there any good algorithms for this?

推荐答案

一种可能是计算排在最后拓扑顺序。该算法是保持其含有有效度（超过节点尚未处理）为零节点的优先级队列。多次出队用最少的标签的节点，其追加订单，递减有效度，其继任者，排队是那些现在在度为零。这将产生1234567890关于btilly的例子，但一般不减少倒。

One possibility is to compute the lexicographically least topological order. The algorithm is to maintain a priority queue containing the nodes whose effective in-degree (over nodes not yet processed) is zero. Repeatedly dequeue the node with the least label, append it to the order, decrement the effective in-degrees of its successors, enqueue the ones that now have in-degree zero. This produces 1234567890 on btilly's example but does not in general minimize inversions.

我喜欢这个算法的性能，输出有一个干净的定义只有一个秩序明显感到满意，并认为，只要有反转（节点x出现节点Y即使X'℃后，Y），X最大的依赖是除Y最大的依赖，这是反转X和Y的借口的各种大。一个自然的推论是，在没有限制的，该法至少顺序排序顺序。

The properties I like about this algorithm are that the output has a clean definition obviously satisfied by only one order and that, whenever there's an inversion (node x appears after node y even though x < y), x's largest dependency is larger than y's largest dependency, which is an "excuse" of sorts for inverting x and y. A corollary is that, in the absence of constraints, the lex least order is sorted order.

这篇关于稳定的拓扑排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！