algorithm - 循环的拓扑排序

Question

我从不同的来源研究如果存在哈密顿路径，则拓扑排序顺序是唯一的；没有其他顺序尊重路径的边缘。如果我们考虑有向图的简单循环，则存在哈密顿路径但不存在拓扑排序，因为每个节点都需要在它之前访问另一个节点。我在这方面有什么遗漏吗？或者它是一个异常(exception)或任何其他事情。提前致谢 。

Answer 1

IIUC，您只是部分引用。以 Wiki entry 为例对此:

If a topological sort has the property that all pairs of consecutive vertices in the sorted order are connected by edges, then these edges form a directed Hamiltonian path in the DAG. If a Hamiltonian path exists, the topological sort order is unique; no other order respects the edges of the path. Conversely, if a topological sort does not form a Hamiltonian path, the DAG will have two or more valid topological orderings, for in this case it is always possible to form a second valid ordering by swapping two consecutive vertices that are not connected by an edge to each other.

所以你的报价

If a Hamiltonian path exists

表示“如果哈密顿路径存在于拓扑排序中”。

因此您的示例的条件在此上下文中无效，因为该图不是 DAG，并且拓扑排序根本不存在