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

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

2012-02-02 Samselvaprabu

https://en.wikipedia.org/wiki/Sorting_algorithm | https：//en.wikipedia.org/wiki/Topological_sorting – 2012-02-02 10:24:06

在抽象层面上它们是连接的：正如Saeed和Stefan所说，它是总订单和部分订单之间的差异。这是一个非常简洁的描述，但有时候在学习时没有帮助。

总的订单意味着，在没有重复的情况下，当您排序某些内容时，您将得到一个唯一的正确答案。如果按升序排序3,6,2，最好得到一个答案：2，3，6.

部分订单有点松散。典型的例子是你穿上衣服的顺序：你可以穿上你的短裤，然后是裤子，然后是你的袜子，然后是你的鞋子。这是一个有效的订单。或者你可以做短裤，袜子，裤子，鞋子。但直觉上，你不能做短裤，裤子，鞋子，袜子。把袜子放在鞋子后面是没有意义的。

为了形式化该敷料示例，您通常会将带有动作（“穿上鞋子”）的依赖关系图显示为节点，并指示显示哪些节点必须位于其他节点之前的依赖关系图。拓扑排序是图形中所有节点的排序，就像尊重弧段一样。意思是，如果从袜子到鞋子都有弧线，那么袜子最好在鞋子前排序。

再次，在抽象层次上，它们是连接的。但他们绝对不是同一件事。

来源

2012-02-02 14:52:48 Novak

如果你是布兰妮，你可以把你的字符串后短...（我已经出局） – Kheldar 2012-02-02 14:54:23

@Novak：非常简单和易于理解的例子。我想我永远不会忘记这种拓扑排序。你是大学教授吗？如果是这样，你的学生真的很幸运。 – Samselvaprabu 2012-02-03 05:48:28

你很善良，但不，我只是一名博士生。我发现我必须在自己的头脑中直接得到低级直觉，以帮助我记住，有时帮助我理解数学描述。数学是抽象力量的地方，但对于我来说，图片和故事就是直觉所在。 – Novak 2012-02-03 19:06:45

拓扑排序通常是指查找符合某个部分顺序的总顺序，例如有向无环图中的可达性关系。

来源

2012-02-02 10:18:38

如果总订单可用，则可以将每个对象与每个对象进行比较。在这种情况下，你可以对wrt进行排序。该订单。示例是wrt的整数。 >（或<或< =，...）或字符串wrt。字典顺序。如果你有一个总的订单排序是可能的。

如果只有部分订单可用，则不是每个对象都可以与其他每个对象进行比较。只有某些对象之间存在关系。一个例子是编译单元之间的依赖关系。拓扑排序是查找对象排序的任务，使得部分顺序得到遵守（例如，通过编译依赖于这些单元之后的某个其他单元的单元）。这里有几种解决方案（即排序）是可能的：如果A取决于B并且存在一些其他单元C，则可能的编译序列是B，A，C和C，A，B（其中A在B之前编译的每个序列）。

来源

2012-02-02 10:20:26 Stefan

在拓扑排序中，我们在partially ordered set上工作，但在正常排序中，我们在total ordered set上工作。

在拓扑排序中，集合中的一对元素之间可能没有任何关系，就像在有向图中一样，在某些节点之间没有任何关系。在正常排序中，集合中的所有元素都有关系。例如，在一组数字中，我们有关系<，>，=所有对之间，所以它是总的有序。

来源

2012-02-02 10:26:12

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

回答

相关问题