检查拓扑排序的有效性

Question

给出以下有向图：

我确定拓扑排序为0, 1, 2, 3, 7, 6, 5, 4，每个节点的值为：

d[0] = 1
f[0] = 16

d[1] = 2
f[1] = 15

d[2] = 3
f[2] = 14

d[3] = 4
f[3] = 13

d[4] = 7
f[4] = 8

d[5] = 6
f[5] = 9

d[6] = 5
f[6] = 10

d[7] = 11
f[7] = 12

d是发现时间，f是终结时间。

如何检查拓扑排序是否有效？

Answer 1

使用python和networkx，您可以按如下方式查看：

import networkx as nx

G = nx.DiGraph()
G.add_edges_from([(0, 2), (1, 2), (2, 3)])
all_topological_sorts = list(nx.algorithms.dag.all_topological_sorts(G))
print([0, 1, 2, 3] in all_topological_sorts) # True
print([2, 3, 1, 0] in all_topological_sorts) # False

但是，请注意，为了进行拓扑排序，图形必须是有向非循环图（DAG）。如果G未被定向，则将引发NetworkXNotImplemented。如果G不是非循环的（如您的情况），将引发NetworkXUnfeasible。

请参阅文档here。

Answer 2

如果你想要一个较少的编码方法来解决这个问题（因为看起来你的原始拓扑排序是在没有代码的情况下生成的），你可以回到拓扑排序的定义。从Emory University转述：

节点的拓扑排序=节点/顶点的排序（标签），使得对于G中的每个边（u，v），u在排序中出现早于v。

有两种方法可以解决这个问题：从顶点透视的边缘角度来看。我描述了一个天真（意味着有一些额外的空间复杂性和聪明，你可以改进它们）以下两者的实现。

边缘方法

迭代G中的边。对于每条边，检索排序中每个顶点的索引。比较指数。如果原点顶点不早于目标顶点，则返回false。如果迭代遍历所有边而不返回false，则返回true。

复杂性：O（E * V）

顶点方法

在您的排序中迭代顶点。对于每个顶点，检索其传出边的列表。如果这些边中的任何一个以在排序中当前顶点之前的顶点结束，则返回false。如果迭代遍历所有顶点而不返回false，则返回true。

复杂性：O（V ^ 2 * E）