graph-theory - 如何检测向有向图添加边是否会导致循环？

Question

我遇到了 wait-for graphs我想知道，是否有任何有效的算法来检测向有向图添加边是否会导致循环？

有问题的图是可变的(它们可以添加或删除节点和边)。而且我们对实际了解一个违规循环并不感兴趣，只知道有一个就足够了(以防止添加违规边缘)。

当然，可以使用计算强连通分量的算法(例如 Tarjan 的)来检查新图是否为无环图，但是每次添加边时再次运行它似乎效率很低。

Answer 1

如果我正确理解了您的问题，那么只有在之前没有从 v 到 u 的路径时才插入新边 (u,v)(即，如果 (u,v) 不创建循环)。因此，您的图始终是 DAG(有向无环图)。在这种情况下，使用 Tarjan 算法来检测强连通分量 ( http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm ) 听起来有点矫枉过正。在插入 (u,v) 之前，您只需要检查是否存在从 v 到 u 的有向路径，这可以通过简单的 BFS/DFS 完成。

因此，最简单的方法如下 (n = |V|, m = |E|):

插入 (u,v):检查是否有从 v 到 u 的路径(BFS/DFS)。时间复杂度: O(米)

删除边:只需将它们从图表中删除即可。时间复杂度: O(1)

尽管在最坏的情况下插入 (u,v) 需要 O(m) 时间，但在您的情况下它可能相当快。当从 v 开始执行 BFS/DFS 以检查 u 是否可达时，您只访问从 v 可达的顶点。我猜想在您的设置中，图形非常稀疏，并且另一个可到达的顶点数量不是高的。

但是，如果您想提高理论运行时间，这里有一些提示(主要表明这不会很容易)。假设我们的目标是在 O(1) 时间内测试是否存在从 v 到 u 的有向路径。此上下文中的关键字是 传递闭包 DAG(即，包含边 (u, v) 的图当且仅当 DAG 中存在从 u 到 v 的有向路径)。不幸的是，在动态设置中维护传递闭包似乎并不那么简单。有几篇论文在考虑这个问题，我找到的所有论文都是STOC或FOCS论文，这表明它们是非常涉及。我发现的最新(也是最快的)结果在论文 中通过动态矩阵逆的动态传递闭包由 Sankowski ( http://dl.acm.org/citation.cfm?id=1033207 )。

即使您愿意了解其中一种动态传递闭包算法(甚至想要实现它)，由于以下原因，它们也不会给您任何加速。这些算法是为这种情况而设计的，在这种情况下，您有很多连接查询(然后可以在 O(1) 时间内执行)并且图中只有很少的变化。目标是使这些更改比重新计算传递闭包更便宜。但是，与单次检查连接相比，此更新仍然较慢。因此，如果您需要对每个连接查询进行更新，最好使用上面提到的简单方法。

那么为什么我要提到这种维护传递闭包的方法，如果它不符合您的需求呢？好吧，它表明搜索仅消耗 O(1) 查询时间的算法可能不会比使用 BFS/DFS 的简单算法更快地找到解决方案。您可以尝试获得比 O(m) 快但比 O(1) 差的查询时间，而更新也比 O(m) 快。这是一个非常有趣的问题，但对我来说听起来像是一个非常雄心勃勃的目标(所以也许不要花太多时间来尝试实现它......)。