如何检查拓扑排序的尝试计算是否确实是其中之一

Question

我需要检查拓扑排序计算是否是下图中的一个：

0->1->2->3
|  ^
v  |
4<-5<-6<-7
5->0
3->6
7->2
i have determines that the topological sorting is: 0 1 2 3 7 6 5 4

如何检查此拓扑排序的计算是否为 1？

Answer 1

您需要测试有序列表中的每个节点n，in传入边缘的每个节点出现在有序列表中的n之前：

isTopologicallySorted(list, graph)
for each n in list
for each in in graph[edges incoming at n]
if list.indexof(in.source) > list.indexof(n) then return false
return true

当然，每个节点应该在列表中只出现一次。