algorithm - 排序和拓扑排序有什么区别？

Question

排序和拓扑排序有什么区别？

它们是相同的还是不同的？

Answer 1

在抽象层面上，它们是相关联的:正如 Saeed 和 Stefan 所说，这是全序和偏序之间的区别。这是一个非常简洁的描述，但有时在您学习时没有帮助。

全序意味着，在没有重复的情况下，当您对某些内容进行排序时，您将得到一个唯一的正确答案。如果你把 3, 6, 2 按升序排列，你最好得到一个答案:2, 3, 6。

偏序稍微宽松一些。典型的例子是你穿衣服的顺序:你可以穿短裤，然后是裤子，然后是 socks ，然后是鞋子。那是一个有效的命令。或者你可以做短裤、 socks 、裤子、鞋子。但直觉上，你不能做短裤、裤子、鞋子、 socks 。穿鞋后再穿 socks 是没有意义的。

为了使该着装示例形式化，您通常会显示一个依赖图，其中将 Action (“穿鞋”)作为节点，并且有向弧显示哪些节点必须先于哪些其他节点。拓扑排序是对图中所有节点的排序，就像尊重弧的排序一样。意思是，如果从 socks 到鞋子有一条弧线，那么 socks 最好在鞋子之前。

因此，在抽象层面上，它们又是相互关联的。但它们绝对不是一回事。