algorithm - 如何查找有向图是否具有两个拓扑顺序？

在我学习了如何确定一个有向图是否有1个拓扑序之后，我有点好奇是否有一种方法可以确定是否有正好有2个拓扑序的图。首先，有两种拓扑类型的图吗？
我学会了使用哈密顿路径来确定DAG是否具有唯一的拓扑排序这在某种程度上适用吗？
谢谢

最佳答案

如果在第（*）行，您可以从两个不同的节点中选择一次-有两个拓扑顺序

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S (*)
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else
    return L (a topologically sorted order)

更准确地说，引用R.Sedgewick的话：
有向图有唯一的拓扑序当且仅当
中每对连续顶点之间的定向边
拓扑序（即有向图有哈密顿路径）。如果
有向图有多个拓扑序，然后是第二个拓扑序
顺序可以通过交换一对连续的顶点来获得。

关于algorithm - 如何查找有向图是否具有两个拓扑顺序？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35399792/