algorithm - 如何实现需要有效收缩和扩展连接组件的图形算法？

Question

有一些算法，比如Edmond's Algorithm , 或 Boruvka's Algorithm这需要程序员创建一个图，该图是通过将一些节点收缩为单个节点，然后再将其扩展回来而获得的。

收缩的正式描述如下:

设 G 是一个顶点为 V 和边为 E 的图。设C 是G 的连通分量。 G 相对于 C 的收缩定义为 V - nodes(C) + C* 上的图，其中 C * 是代表契约组件的“ super 节点”。 C 中不涉及顶点的边保持原样。在 C 中具有端点的边现在连接到 C*。

我不清楚如何使用邻接列表等表示来实现此类算法原语。

什么是一种优雅而有效的方式来表示图形，以便它们可以收缩，同时记住相关数据以展开它们？

Answer 1

我会使用 disjoint-set 数据结构也称为联合查找 数据结构。最初将每个顶点想象成一个集合。现在的工作是这样的:

对于收缩:取参与所有收缩的所有顶点的并集。集合中的所有顶点都由称为所有顶点的父节点的单个顶点表示，您可以将其称为 super 节点。该链接包含有关如何执行此操作的所有详细信息。

对于 expansion 只需执行相反的操作，在最坏的情况下，您必须使每个顶点代表一个集合。所以基本上这种方法适用于非重叠集合操作。