如何查找有向图是否有两个拓扑排序？

Question

在我学会了如何确定有向图是否具有1个拓扑排序之后,如果有一种方法可以确定是否存在具有2个拓扑排序的图,我有点好奇.首先,是否存在具有2个拓扑排序的图的真实情况？

我学会了使用哈密尔顿路径来确定DAG是否具有唯一的拓扑排序.这是否适用于此？谢谢

Answer 1

如果在行(*)处,您可以从2个不同的节点中选择一次 - 有两个拓扑排序

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:

当且仅当在拓扑顺序中每对连续顶点之间存在有向边(即,有向图具有哈密顿路径)时,有向图具有唯一的拓扑排序.如果有向图具有多个拓扑排序,则可以通过交换一对连续顶点来获得第二拓扑顺序.