用于查找引发循环的所有边的高效算法
Efficient algorithm for finding all edges that induce a cycle
找到所有边的最快方法是什么，如果添加到图中，会在有向无环图中引发循环？
形式上： 假设你有一个边集 $E\subset V\times V$ 的 DAG $G=(V,E)$。找到所有 $e\in V\times V-E$ 使得图 $G(e)=(V,E\cup{e})$ 至少有一个循环。
蛮力方法是使用 DFS 检查 $G(e)$ 是否有所有 $e\in V\times V-E$ 的循环。有没有更快的方法？
对于每个节点 X、DFS 或 BFS，它的父节点和父节点等。这些边中的每一个（从 X 到它的任何父节点）都会创建一个循环。
性能为 O(c) + O(|V|)，其中 c 是会引发循环的边数。
我也建议你尝试实现拓扑排序，这对你来说是一个很好的实践，并且是一个类似的概念。
观察：当且仅当[它是一个自循环或其反向边缘属于DAG的transitive closure]时，一条边会引发一个循环。因此，计算传递闭包的问题本质上等同于这个问题。遗憾的是，理论上最快的已知算法是基于快速矩阵乘法，因此非常不切实际。
如果您有兴趣在实践中计算大型 DAG 的传递闭包，维基百科链接到 Esko Nuutila's thesis on the subject。
找到所有边的最快方法是什么，如果添加到图中，会在有向无环图中引发循环？
形式上： 假设你有一个边集 $E\subset V\times V$ 的 DAG $G=(V,E)$。找到所有 $e\in V\times V-E$ 使得图 $G(e)=(V,E\cup{e})$ 至少有一个循环。
蛮力方法是使用 DFS 检查 $G(e)$ 是否有所有 $e\in V\times V-E$ 的循环。有没有更快的方法？
对于每个节点 X、DFS 或 BFS，它的父节点和父节点等。这些边中的每一个（从 X 到它的任何父节点）都会创建一个循环。 性能为 O(c) + O(|V|)，其中 c 是会引发循环的边数。
我也建议你尝试实现拓扑排序，这对你来说是一个很好的实践，并且是一个类似的概念。
观察：当且仅当[它是一个自循环或其反向边缘属于DAG的transitive closure]时，一条边会引发一个循环。因此，计算传递闭包的问题本质上等同于这个问题。遗憾的是，理论上最快的已知算法是基于快速矩阵乘法，因此非常不切实际。
如果您有兴趣在实践中计算大型 DAG 的传递闭包，维基百科链接到 Esko Nuutila's thesis on the subject。