如何实现需要高效缩放和扩展连接组件的图算法？

Question

有一些算法，例如Edmond's Algorithm或Boruvka's Algorithm，需要程序员创建一个图形，该图形是通过将一些节点合并为单个节点而获得的，并在稍后将其扩展回来。

收缩的正式描述如下：

假设G是具有顶点V和边缘E的图形。 让C是G的连通组件。 关于C的G的收缩定义为在V-nodes（C）+ C * 上的图形，其中C * 是代表已缩小的组件的“超级节点”。 不涉及C中的顶点的边缘保持不变。 现在将端点在C中的边缘连接到C *。

我不清楚如何使用邻接表等表示方法来实现这样的算法原语。

有什么优雅高效的方法可以表示图，以便在缩小它们的同时记住扩展所需的相关数据？

- Agnishom Chattopadhyay

---

一个“合并的”节点可以成为一个更大的“合并”的节点的一部分吗？也就是说，“超级节点”可以嵌套吗？ - Eric Lippert

@EricLippert 是的。在实现Edmond算法时，这样的结构可能是必要的，其中可能会有多个递归调用。 - Agnishom Chattopadhyay

通常有一种非常简单的方法，取决于实现的其他细节，即最佳方法通常不是适用于大多数算法或它们的大多数实现的通用方法。 - Matt Timmermans

对于一般情况，最接近的东西是用于动态图中连接查询的数据结构（https://en.wikipedia.org/wiki/Dynamic_connectivity#General_graphs_2）。维基百科称，可以在每个操作中以多项式对数时间支持动态连接查询（包括无向图中的边缘删除和插入）。 - Neal Young

Answer 1

我会使用称为“并查集”数据结构的disjoint-set 数据结构。最初，将每个顶点视为一个集合。现在的工作方式如下：

对于“收缩”：取参与所有收缩的顶点的并集。所有集合中的顶点由称为所有顶点父节点的单个顶点表示，您可以将其称为超级节点。链接中详细介绍了如何做到这一点。

对于扩展，只需进行反向操作，在最坏情况下，您需要使每个顶点表示一个单独的集合。因此，基本上这种方法适用于不重叠的集合操作。

- Sumeet

---

在我所知道的并查集数据结构中，Union 操作不容易反转。Find 操作会修改数据结构（例如，在跟踪 Find 的路径时，Find 会将每个指针更改为指向当前根节点）。这是为了提高效率而必要的。鉴于 Find 操作会修改数据结构并且会丢失信息，您如何考虑有效地进行扩展？ - Neal Young

@NealYoung，你所说的是路径压缩启发式算法吗？然而，我只是指出了可行的数据结构方向。但即使在文献中也没有提到反转，因此我将其留给OP来实现细节。 - Sumeet

是的，路径压缩是你在维基百科链接中描述的数据结构所要求的。有人知道你留给OP的实现细节吗？据我所知没有。 - Neal Young

@NealYoung 当你实际使用集合时，你会经常使用查找以达到优化，但在这里你要么收缩要么扩展。就像我说的，我只是根据输入指出了一个方向。 - Sumeet

Answer 2

首先，我喜欢Sumeet Singh的答案，你可能首先探索这个想法。我有一个类似的想法，但细节略有不同。

不幸的是，我现在不在一个可以画图的地方，这真的会帮助到这里。让我尝试清楚地描述我心中所想。

解决方案涉及创建两种新节点：

- “超级节点”代表收缩集 - “转发节点”是超级节点的代理，知道如何“撤消”其创建。 - 转发节点有三个引用：指向其超级节点、其“外部”节点和其“内部”节点。 - 超级节点具有其所有转发节点的列表。

收缩：

考虑您的连通分量G。

- 创建表示此连通分量的“超级节点”。 - 对于G中的每个节点，可能存在连接到不在G中的节点的边缘。称这些边为e1、e2、e3等。 - 为每个这些边创建转发节点F1、F2、F3…。 - 现在对于这些边的每一个，假设e1是从A1（不在G中）到B1（在G中）的。从图中删除A1-B1边缘，添加A1-F1边缘。A1成为F1的外部节点，B1成为F1的内部节点。

扩张只是相反的：

- 对于超级节点中的每个转发节点F，删除从外部节点到它的边缘，添加从外部节点到内部节点的边缘，并删除所有转发节点。 - 删除超级节点。

关键在于实现图形操作。如果您向转发节点询问“你的邻居是谁”，它必须将该请求转发给超级节点，而超级节点必须说“所有我的转发节点的外部节点”。依此类推。

- Eric Lippert

---

我在想，把转发节点 internal 化到超级节点里面会不会更简单一些，而不是让它们坐在超级节点周围。这样所有其他节点都会看到自己连接到了超级节点，你也就不需要再担心转发问题了。你仍然需要转发节点将内部节点连接到外部边缘，但只有当你扩展超级节点或从内部转换到外部（或反之）时，它们才需要发挥作用。 - Wearwolf

@Wearwolf：当然，有很多方法可以解决这个问题。但关键是：（1）某个数据结构知道链接曾经是什么，并可以恢复它们，（2）无论那个东西是什么，在传入边的角度上看起来像一个顶点。 - Eric Lippert