检查新边是否会使 DAG 循环
Check if new edge will make DAG cyclic
给定一些有向图，有很多算法可以检查天气是否包含循环。即具有这样签名的算法：
function isCyclic(g: DirectedGraph): bool
但我有一个有点不同的问题：给定一个我已经知道是非循环的有向图，我想检查添加给定边是否会创建一个循环。即是这样的：
function willCreateCycle(g: AcyclicDirectedGraph, newEdge: Edge): bool
到目前为止我的解决方案：
在图中我们有一些节点，其中两个是 F（从）和 T（到）
我们要检查添加新边 E = F->T 是否会创建一个循环
=>
从节点 T 开始遍历图。如果我们在任何一点结束于节点 F，我们就有一个循环。
大家觉得这样对吗？ :))
是的，这是正确的。当且仅当已经存在从 T 到 F 的路径时，添加边 F->T 将导致循环。
给定一些有向图，有很多算法可以检查天气是否包含循环。即具有这样签名的算法：
function isCyclic(g: DirectedGraph): bool
但我有一个有点不同的问题：给定一个我已经知道是非循环的有向图，我想检查添加给定边是否会创建一个循环。即是这样的：
function willCreateCycle(g: AcyclicDirectedGraph, newEdge: Edge): bool
到目前为止我的解决方案：
在图中我们有一些节点，其中两个是 F（从）和 T（到） 我们要检查添加新边 E = F->T 是否会创建一个循环
=>
从节点 T 开始遍历图。如果我们在任何一点结束于节点 F，我们就有一个循环。
大家觉得这样对吗？ :))
是的，这是正确的。当且仅当已经存在从 T 到 F 的路径时，添加边 F->T 将导致循环。