如何查找有向图是否具有两个拓扑排序？
How to find if a directed graph has two topological ordering?
在学习了如何判断一个有向图是否有1个拓扑序之后，我有点好奇是否有一种方法可以判断是否有恰好有2个的图。首先是否真的有图有 2 个拓扑排序？
我学会了使用哈密顿路径来确定 DAG 是否具有唯一的拓扑排序。这是否适用于此？
谢谢
如果在 (*) 行，您可以从 2 个不同的节点 select 一次 - 有两个拓扑排序
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：
A digraph has a unique topological ordering if and only if there is a
directed edge between each pair of consecutive vertices in the
topological order (i.e., the digraph has a Hamiltonian path). If the
digraph has multiple topological orderings, then a second topological
order can be obtained by swapping a pair of consecutive vertices.
在学习了如何判断一个有向图是否有1个拓扑序之后，我有点好奇是否有一种方法可以判断是否有恰好有2个的图。首先是否真的有图有 2 个拓扑排序？
我学会了使用哈密顿路径来确定 DAG 是否具有唯一的拓扑排序。这是否适用于此？ 谢谢
如果在 (*) 行，您可以从 2 个不同的节点 select 一次 - 有两个拓扑排序
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：
A digraph has a unique topological ordering if and only if there is a directed edge between each pair of consecutive vertices in the topological order (i.e., the digraph has a Hamiltonian path). If the digraph has multiple topological orderings, then a second topological order can be obtained by swapping a pair of consecutive vertices.