graph - 具有唯一拓扑排序的图的先决条件

Question

让我们假设有问题的图是 DAG(有向无环图)。

问题 :我能否得出结论，当且仅当只有一个顶点没有传入边时，这样的图才会具有唯一的拓扑排序？

换句话说，是否只有一个没有传入边的顶点需要(但还不够)来生成唯一的拓扑排序？

Answer 1

当且仅当在拓扑顺序中的每对连续顶点之间存在有向边(即有向图具有 Hamiltonian path)时，拓扑排序才是唯一的。 Source

哈密​​顿路径只是意味着两个顶点之间的路径只会访问每个顶点一次，这并不意味着一个顶点必须没有传入边。你可以有一条实际上是 cycle 的哈密顿路径.这仍然会生成一个独特的拓扑排序(当然，如果这对您很重要，它也将是一个循环)。

希望这可以帮助