Pet*_*lák 32 graph-theory directed-graph cyclic-graph
我想到等待图表,我想知道,是否有任何有效的算法来检测是否向有向图添加边缘会导致循环？
有问题的图是可变的(它们可以添加或删除节点和边).而且我们对实际知道一个有问题的周期并不感兴趣,只知道有一个是足够的(以防止添加一个有问题的边缘).
当然,可以使用算法来计算强连接组件(例如Tarjan)以检查新图是否是非循环的,但每次添加边时再次运行它似乎效率很低.
Tho*_*mas 35
如果我正确地理解了你的问题,那么只有在之前没有从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)需要花费O(m)的时间,但在你的情况下可能会非常快.当从v开始执行BFS/DFS以检查是否可以访问时,您只访问可从v访问的顶点.我猜想在您的设置中,图形非常稀疏,并且另一个可到达的顶点数不是那个高.
但是,如果你想改善理论运行时间,这里有一些提示(大多数表明这不会很容易).假设我们的目标是在O(1)时间内测试是否存在从v到u的有向路径.此上下文中的关键字是DAG 的传递闭包(即,当且仅当在DAG中存在从u到v的有向路径时,包含边(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)快.这是一个非常有趣的问题,但在我看来这是一个非常雄心勃勃的目标(所以也许不要花太多时间去尝试实现它......).
正如Mark建议的那样,可以使用存储连接节点的数据结构.最好使用布尔矩阵|V|x|V|.可以使用Floyd-Warshall算法初始化值.这是完成的O(|V|^3).
让我们T(i)来设置有路径到顶点顶点i,并F(j)设置在从顶点存在路径顶点j.首先是第一行中的真实i,第二列中是第二行j.
添加边缘(i,j)是简单的操作.如果之前i和j之前没有连接过,那么每个afrom T(i)和bfrom 都会从F(j)set matrix元素(a,b)变为true.但操作并不便宜.在最坏的情况下它是O(|V|^2).这是在有向线的情况下,并且从末端到起始顶点添加边缘使得所有顶点连接到所有其他顶点.
卸下边缘(i,j)不是那么简单,但在最坏的情况下,不贵多操作:-)如果从一个路径i,以j去除边缘后,比没有什么变化.用Dijkstra检查,不到O(|V|^2).不再连接的顶点是(a,b):
ain T(i)- i- T(j),b在F(j)+j仅T(j)在删除边缘时更改(i,j),因此必须重新计算.这是通过任何类型的图遍历(BFS,DFS),通过从顶点沿相反的边缘方向进行的j.那是在不到那时完成的O(|V|^2).由于矩阵元素的设置在最坏情况下也是如此O(|V|^2),因此该操作具有与添加边缘相同的最坏情况复杂度.