如何判断向 DAG 中添加边是否形成有向循环?
How to tell if adding an edge to a DAG forms a directed cycle?
假设我有一个 DAG 和图中每个顶点 v 的给定拓扑顺序函数,当查看 2 个特定节点时:x,y 我知道 |top(x)-top(y)|< 10 如何判断添加边 x->y 是否会在图中形成循环?
我正在尝试实现比 O(V+E) 更好的解决方案...
我的想法是检查是否 top(x) > top (y),如果是,那么我们创建了一个循环。
但恐怕我可能会错过一个案例,而且 |top(x)-top(y)|<10 是否给我任何其他信息?有什么启示吗?
它确实漏掉了一个案例。
>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
,所以我们可以在遍历时忽略其他节点。
我们可以利用 |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 和图中每个顶点 v 的给定拓扑顺序函数,当查看 2 个特定节点时:x,y 我知道 |top(x)-top(y)|< 10 如何判断添加边 x->y 是否会在图中形成循环? 我正在尝试实现比 O(V+E) 更好的解决方案...
我的想法是检查是否 top(x) > top (y),如果是,那么我们创建了一个循环。 但恐怕我可能会错过一个案例,而且 |top(x)-top(y)|<10 是否给我任何其他信息?有什么启示吗?
它确实漏掉了一个案例。
>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
,所以我们可以在遍历时忽略其他节点。
我们可以利用 |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]
为真。