如何查找有向圖是否有兩個拓撲排序？

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.塞奇威克：

有向圖有一個獨特的拓撲排序當且僅當沒有在 拓撲次序（即，有向圖具有漢彌爾頓路徑）每對連續的頂點之間的 向邊。如果有向圖 具有多個拓撲排序，然後進行第二次拓撲 順序可以通過交換一對連續的頂點獲得。