sorting - 所有 DAG 具有多个拓扑排序顺序的原因

Question

我想知道为什么所有有向无环图都有不止一个拓扑排序顺序。

我搜索了谷歌并说大部分内容只是轻而易举地发现他们至少有一种拓扑排序。但我正在考虑如何实现单链表：

A -> B -> C -> D

这可能意味着拓扑排序在技术上只能通过一种方式 - D、C、B、A ......

但是，这可能不是有向无环图，但我不确定如何反驳这种情况，因为它是有向的（A 到 B 等），无环（没有返回任何起点的循环）图（从技术上讲，它是一棵树）..

非常感谢您提供的任何澄清！

标签： sortinggraphdirected-acyclic-graphstopological-sort

Answer 1

并非所有 DAG 都具有不止一种拓扑排序。请记住，我们可以通过按顺序删除没有传入边的顶点来构造拓扑排序。

考虑一个 DAG，它包含一条连接其所有顶点的连续路径（请注意，此路径不会形成循环，否则不会是 DAG）。我们可以从删除没有传入边的顶点开始，然后重复。我们会发现拓扑排序在每对连续的顶点之间都有一条边。如果我们想形成另一种拓扑排序，我们可以从删除一些没有传入边的其他顶点开始，但这意味着至少有 2 个没有传入边的边，在这种情况下，不可能开始一个从一个顶点开始的路径并连接所有其他顶点。

由于我们从一个有连接所有顶点的路径的 DAG 开始，我们遇到了矛盾。因此，证明具有连接所有顶点的路径的 DAG 将具有唯一的拓扑排序。