algorithm - 检查一个变化的无向图是否至少有一个圆

Question

我有一个最初没有边的无向图。现在在每一步中都会添加或删除一条边，并且必须检查图形是否至少有一个圆。可能最简单的充分条件是

连通分量 + 边数 <= 节点数。

由于我上面提到的“步骤”执行了数百万次，因此此检查必须非常快。所以我想知道什么是一种快速检查条件的方法，这取决于在每个步骤中只有一个边缘发生变化这一事实。

有什么建议吗？

Answer 1

如果您有兴趣，可以尝试实现一个完全动态的图形连接数据结构，如 "Poly-logarithmic deterministic fully-dynamic graph algorithms I: connectivity and minimum spanning tree" by Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup 中所述。 .

添加边时，检查两个端点是否相连。如果不是，则连接组件的数量减少一个。删除边后，检查两个端点是否仍然连接。如果不是，则连接组件的数量增加一个。边插入和删除的分摊运行时间为 O(log^2 n)，但我可以想象常数因子相当高。

有newer result有更好的界限。还有一个 experimental evaluation一些动态连接算法也考虑了实现细节。还有一个Javascript implementation .我不知道它有多好。

我想在实践中，您可以通过维护生成的森林来轻松得多。您(几乎)免费获得边添加和非树边删除。对于树边删除，您可以使用 BFS 或 DFS 形式的“蛮力”来检查端点是否仍然连接。特别是如果节点的数量是有界的，也许在实践中效果很好，BFS 和 DFS 对于密集图都是 O(n^2) 并且您可以将其中的一些工作分配给操作你很幸运，没有太多事可做。