如何判断向 DAG 中添加边是否形成有向循环？

Question

假设我有一个 DAG 和图中每个顶点 v 的给定拓扑顺序函数，当查看 2 个特定节点时：x，y 我知道 |top(x)-top(y)|< 10 如何判断添加边 x->y 是否会在图中形成循环？我正在尝试实现比 O(V+E) 更好的解决方案...

我的想法是检查是否 top(x) > top (y)，如果是，那么我们创建了一个循环。但恐怕我可能会错过一个案例，而且 |top(x)-top(y)|<10 是否给我任何其他信息？有什么启示吗？

Answer 1

它确实漏掉了一个案例。

     >x
    /
  >v
 /
r
 \
  >y

0  1  2

其中 top(r) = 0 和 top(v) = top(y) = 1 以及 top(x) = 2。连接x->y还好，但是top功能要改

我们所知道的是，如果已经有一条从 y 到 x 的路径，那么中间节点的 top 少于 x，所以我们可以在遍历时忽略其他节点。

Answer 2

我们可以利用 |top(x) < top(y)| < 10 这一事实来找到有效的解决方案。

首先，注意如果top(x) < top(y)没有循环。否则，设 ar[] = y, z₁, z₂ … z_k, x 为 y 和 x 之间拓扑排序中的节点。如果存在一条从y到x的路径，它只能经过这些顶点。所以只要检查是否有路径：

haspath[] = {false}
haspath[1] = true
for i = 2 to k+2
  for j = 1 to i-1
    if haspath[j]==true and edge(ar[j],ar[i])
      haspath[i] = true
      break

存在一条从 y 到 x 的路径当且仅当 haspath[k+2] 为真。

如何判断向 DAG 中添加边是否形成有向循环？

How to tell if adding an edge to a DAG forms a directed cycle?

algorithm

directed-acyclic-graphs

topological-sort

sanity-check