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

Question

有一些算法,如Edmond算法或Boruvka算法,它要求程序员创建一个图形,该图形是通过将一些节点收缩到一个节点中,然后再将其扩展回来获得的.

收缩的正式描述如下:

让我们G与顶点的图V和边E.让我们C成为一个连接组件G.G相对于的收缩C被定义为图形V - nodes(C) + C*,其中C*是表示收缩组分的"超级节点".不涉及顶点的边缘C是原样的.C现在连接有端点的边C*.

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

什么是一种优雅而有效的方式来表示图形,以便它们可以签约,同时记住用于扩展它们的相关数据？

Answer 1

我将使用不相交集数据结构，也称为union\xe2\x80\x93find数据结构。最初将每个顶点想象为一个集合。现在工作是这样的：

\n\n

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

\n\n

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

\n