排序和拓扑排序有什么区别?
它们是相同的还是不同的?
最佳答案
在抽象层面上,它们是相关联的:正如 Saeed 和 Stefan 所说,这是全序和偏序之间的区别。这是一个非常简洁的描述,但有时在您学习时没有帮助。
全序意味着,在没有重复的情况下,当您对某些内容进行排序时,您将得到一个唯一的正确答案。如果你把 3, 6, 2 按升序排列,你最好得到一个答案:2, 3, 6。
偏序稍微宽松一些。典型的例子是你穿衣服的顺序:你可以穿短裤,然后是裤子,然后是 socks ,然后是鞋子。那是一个有效的命令。或者你可以做短裤、 socks 、裤子、鞋子。但直觉上,你不能做短裤、裤子、鞋子、 socks 。穿鞋后再穿 socks 是没有意义的。
为了使该着装示例形式化,您通常会显示一个依赖图,其中将 Action (“穿鞋”)作为节点,并且有向弧显示哪些节点必须先于哪些其他节点。拓扑排序是对图中所有节点的排序,就像尊重弧的排序一样。意思是,如果从 socks 到鞋子有一条弧线,那么 socks 最好在鞋子之前。
因此,在抽象层面上,它们又是相互关联的。但它们绝对不是一回事。
关于algorithm - 排序和拓扑排序有什么区别?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9110459/