Sam*_*abu 5 sorting algorithm computer-science topological-sort
排序和拓扑排序有什么区别？
它们是相同还是不同？
在抽象层面上,它们是相互联系的:正如Saeed和Stefan所说,这是总订单和部分订单之间的差异.这是一个非常简洁的描述,但有时在你学习时没有帮助.
总订单意味着,在没有重复的情况下,当您对某些内容进行排序时,您将获得一个独特的正确答案.如果按升序排序3,6,2,最好得到一个答案:2,3,6.
部分订单稍微宽松一些.典型的例子是你穿上衣服的顺序:你可以穿短裤,然后是裤子,袜子,鞋子.这是一个有效的订单.或者你可以做短裤,袜子,裤子,鞋子.但直觉上,你不能做短裤,裤子,鞋子,袜子.鞋子穿上袜子是没有意义的.
为了使该修整示例正式化,您通常会显示一个依赖关系图,其中包含操作("穿上鞋子")作为节点,以及显示哪个节点必须先于其他节点的有向弧.拓扑排序是图中所有节点的排序,如同尊重弧的节点.意思是,如果从袜子到鞋子都有弧形,那么袜子最好在鞋子之前.
因此,在抽象层面上,它们是相互联系的.但它们绝对不是一回事.