如何检测将边添加到有向图是否导致循环? [英] How to detect if adding an edge to a directed graph results in a cycle?

问题描述

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

I came upon wait-for graphs and I wonder, are there any efficient algorithms for detecting if adding an edge to a directed graph results in a cycle?

所讨论的图形是可变的(它们可以添加或删除节点和边).而且，我们对知道一个犯罪周期并不感兴趣，只是知道一个周期就足够了(以防止增加一个犯罪边缘).

The graphs in question are mutable (they can have nodes and edges added or removed). And we're not interested in actually knowing an offending cycle, just knowing there is one is enough (to prevent adding an offending edge).

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

Of course it'd be possible to use an algorithm for computing strongly connected components (such as Tarjan's) to check if the new graph is acyclic or not, but running it again every time an edge is added seems quite inefficient.

推荐答案

如果我正确理解了您的问题，则仅当以前没有从v到u的路径时(例如，如果(u，v)不会创建一个循环).因此，您的图始终是DAG(有向无环图).使用Tarjan算法来检测紧密连接的组件( http://en.wikipedia.org/wiki/Tarjan%在这种情况下，27s_strongly_connected_components_algorithm )听起来像是过分杀伤力.在插入(u，v)之前，您需要检查的是是否存在从v到u的定向路径，这可以通过简单的BFS/DFS来完成.

If I understood your question correctly, then a new edge (u,v) is only inserted if there was no path from v to u before (i.e., if (u,v) does not create a cycle). Thus, your graph is always a DAG (directed acyclic graph). Using Tarjan's Algorithm to detect strongly connected components (http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm) sounds like an overkill in this case. Before inserting (u,v), all you have to check is whether there is a directed path from v to u, which can be done with a simple BFS/DFS.

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

So the simplest way of doing it is the following (n = |V|, m = |E|):

• 插入(u，v):检查是否存在从v到u的路径(BFS/DFS).时间复杂度: O(m)
• 删除边缘:只需将其从图形中删除即可.时间复杂度: O(1)

• Inserting (u,v): Check whether there is a path from v to u (BFS/DFS). Time complexity: O(m)
• Deleting edges: Simply remove them from the graph. Time complexity: O(1)

尽管在最坏的情况下插入(u，v)会花费O(m)时间，但在您的情况下这可能会非常快.当从v开始执行BFS/DFS以检查u是否可访问时，您仅访问从v可访问的顶点.我猜想在您的设置中，图形相当稀疏，而另一个可访问的顶点的数目不是高.

Although inserting (u,v) takes O(m) time in the worst case, it is probably pretty fast in your situation. When doing the BFS/DFS starting from v to check whether u is reachable, you only visit vertices that are reachable from v. I would guess that in your setting the graph is pretty sparse and that the number of vertices reachable by another is not that high.

但是，如果您想改善理论上的运行时间，这里有一些提示(主要表明这并不容易).假设我们的目标是在O(1)时间内测试是否存在从v到u的定向路径.在这种情况下，关键字是DAG的传递闭包(即，当且仅当DAG中存在从u到v的定向路径时，包含边(u，v)的图) .不幸的是，将传递闭包保持在动态环境中似乎并不那么简单.有数篇论文都在考虑这个问题，我发现的所有论文都是STOC或FOCS论文，这表明它们非常.我发现的最新(最快)结果是Sankowski(

However, if you want to improve the theoretical running time, here are some hints (mostly showing that this will not be very easy). Assume we aim for testing in O(1) time whether there exists a directed path from v to u. The keyword in this context is the transitive closure of a DAG (i.e., a graph that contains an edge (u, v) if and only if there is a directed path from u to v in the DAG). Unfortunately, maintaining the transitive closure in a dynamic setting seems to be not that simple. There are several papers considering this problem and all papers I found were STOC or FOCS papers, which indicates that they are very involved. The newest (and fastest) result I found is in the paper Dynamic Transitive Closure via Dynamic Matrix Inverse by Sankowski (http://dl.acm.org/citation.cfm?id=1033207).

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

Even if you are willing to understand one of those dynamic transitive closure algorithms (or even want to implement it), they will not give you any speed up for the following reason. These algorithms are designed for the situation, where you have a lot of connectivity queries (which then can be performed in O(1) time) and only few changes in the graph. The goal then is to make these changes cheaper than recomputing the transitive closure. However, this update is still slower that a single check for connectivity. Thus, if you need to do an update on every connectivity query, it is better to use the simple approach mentioned above.

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

So why do I mention this approach of maintaining the transitive closure if it does not fit your needs? Well, it shows that searching an algorithm consuming only O(1) query time does probably not lead you to a solution faster than the simple one using BFS/DFS. What you could try is to get a query time that is faster than O(m) but worse than O(1), while updates are also faster than O(m). This is a very interesting problem, but it sounds to me like a very ambitious goal (so maybe do not spend too much time on trying to achieve it..).

这篇关于如何检测将边添加到有向图是否导致循环?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！