39

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

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

当然，可以使用一种算法来计算强连接组件（例如 Tarjan 的）来检查新图是否是非循环的，但是每次添加边时再次运行它似乎效率很低。

4

4 回答 4

41

如果我正确理解了您的问题，那么只有在之前没有从 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(m)
  • 删除边：只需将它们从图中删除。时间复杂度：O(1)

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

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

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

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

于 2013-11-30T08:36:24.857 回答
5

正如 Mark 所建议的，可以使用存储连接节点的数据结构。最好使用布尔矩阵|V|x|V|。可以使用 Floyd–Warshall 算法初始化值。这是在O(|V|^3).

让T(i)一组具有到 vertex 的路径的顶点i，以及F(j)从 vertex 存在路径的一组顶点j。第一个是第 'th 行中的 true's和第 'th 列i中的第二个 true's j。

添加边缘(i,j)是简单的操作。如果i之前j没有连接，则对于每个afromT(i)和每个bfrom都F(j)将矩阵元素设置(a,b)为 true。但操作并不便宜。在最坏的情况下它是O(|V|^2)。那是在有向线的情况下，从端点添加边到开始顶点会使所有顶点连接到所有其他顶点。

移除边缘并不是那么简单，但在最坏的情况下不会更昂贵的操作:-) 如果在移除边缘之后(i,j)有一条从i到的路径，那么什么都不会改变。j用 Dijkstra 检查，小于O(|V|^2). 不再连接的顶点是(a,b)：

  • a在T(i)- i- T(j),
  • b在F(j)+j

OnlyT(j)会随着移除 edge 而改变(i,j)，因此必须重新计算。这是通过任何类型的图遍历（BFS，DFS），通过从 vertex 沿相反的边缘方向来完成的j。那是在 less 内完成的O(|V|^2)。由于矩阵元素的设置再次处于最坏情况下O(|V|^2)，因此该操作具有与添加边相同的最坏情况复杂度。

于 2013-11-29T20:36:25.823 回答
0

如果所有以前的作业都按拓扑排序。然后，如果您添加一条看起来会阻碍排序并且无法修复的边，那么您就有了一个循环。

https://stackoverflow.com/a/261621/831850

因此，如果我们有一个排序的节点列表：

1, 2, 3, ..., x, ..., z, ...
Such that each node is waiting for nodes to its left.

假设我们要从 x->z 添加一条边。好吧，这似乎阻碍了这种排序。因此，我们可以将 x 处的节点移动到位置 z+1，如果没有节点 (x, z] 与 x 处的节点有边，这将修复排序 i。

于 2013-12-06T16:24:36.570 回答
0

如果图形是定向的，您只需检查新边应该开始的节点的父节点（向上导航直到到达根节点）。如果其中一个父节点等于边的末端，则添加边将创建一个循环。

于 2013-12-06T16:45:44.600 回答