0

所以我在尝试实现一个功能时遇到了这个问题：

假设我有一个随机的、无向的节点图，其中一些节点相互连接。

让我们将沿某条路径彼此可达的每一组节点称为一个集合。

现在，让我们假设图只包含一个这样的集合（即，每个节点都可以从其他节点到达）。

如果我取一个随机节点 A 并将其从集合中删除，我需要快速有效地确定保留哪些集合。如果 A 是集合中的一个切点，则删除它应该将集合拆分为两个或更多个更小的集合。我只需要一种有效的方法来做两件事：

  • 从集合中移除 A 并确定剩余集合，以及
  • 添加一个新节点 B，其中任意数量的新边将其连接到其他节点。

我需要能够适度快速地执行这两个操作。本质上，我正在寻找 O(log(n)) 或 O(1) 解决方案。O(n) 解决方案是不可接受的，因为该图可能很大。我并不特别关心内存开销。谁能指出我在这里使用哪种数据结构/算法的正确方向？我已经考虑过 Union-Find 和 Djikstra 之类的东西，但它们不适合我的需要。我不想在每次添加或删除节点时对整个图进行完整的连接检查。

4

1 回答 1

1

Henzinger 和 King有一篇非常好的论文。我认为它直接回答了你的问题。

此方法在每次删除边时分摊了 O(log^3(n)) 复杂度（删除顶点等于删除与其相关的所有边）和每个查询 O(log(n) / loglog(n)) 最坏情况复杂度（v 和 u 在同一个连通分量中）。

此外，这个问题有很多变体，例如，如果只允许删除，您可以更快地完成。

于 2013-06-16T23:30:08.837 回答