具有多个排序解的DAG的唯一拓扑排序

Question

我有一个DAG(有向无环图)，它有多个有效的拓扑排序。我正在寻找一种方法来对它进行拓扑排序，并应用二级排序，以始终获得相同的，定义良好的结果。

举个例子:

B

,>

C ->

D

B——>

C -> D

拓扑排序有两个解:

1: A, B, C, D和

2: A, C, B, D

我们注意到B和C可以按任意顺序排序。因此，我们选择字母排序作为二级排序，只得到一个解:A, B, C, d。

这可以推广到任何DAG吗?如何实现?

Answer 1

所以你问的问题更多是指编程语义而不是算法本身。拓扑排序算法在其基本级别上假定用户将调整算法以考虑他/她可能需要算法做的任何事情。因此，为了得到ABCD解而不是ACBD解，您需要在算法中断言，在有两个可能候选的情况下，将选择具有字母优先级的字符。为了将它推广到任何DAG，你只需要在你的算法中指定它。

另一方面，如果您希望确保每次不会选择相同的节点顺序，则可以在有多个候选节点时随机选择节点的方式。

Answer 2

不能使用带有tie-breaker函数的标准拓扑排序吗?也就是说，不要使用DFS方法，而是迭代地(或递归地)删除和排队顶点，没有剩余的限制。每次有多个不受限制的顶点可用时，使用tie-breaker函数在它们之间进行选择。你的tie breaker函数会(我理解你的问题)简单地选择其标签按字母顺序出现的顶点。