高效性能基于标准的图形压缩

Question

我有一个有向加权的简单图。我想将每个节点值相等的节点与另一个直接连接到它的节点收缩。收缩后，平行边将与权重之和合为一。

做这件事最有效的方法/算法是什么？我的图被存储为邻接列表，如果这会改变答案的话。

Answer 1

如果您被允许创建一个新的图，但不想在原地执行此操作，则可以使用并集查找数据结构：https://en.wikipedia.org/wiki/Disjoint-set_data_structure会在这里帮你的。

此结构允许您为合并在一起的每组顶点定义一个代表性顶点。在这组顶点上创建新图形，并使用并集查找结构在此新图形上创建边。