有一些算法,比如Edmond's Algorithm , 或 Boruvka's Algorithm这需要程序员创建一个图,该图是通过将一些节点收缩为单个节点,然后再将其扩展回来而获得的。
收缩的正式描述如下:
设 G
是一个顶点为 V
和边为 E
的图。设C
是G
的连通分量。 G
相对于 C
的收缩定义为 V - nodes(C) + C*
上的图,其中 C *
是代表契约组件的“ super 节点”。 C
中不涉及顶点的边保持原样。在 C
中具有端点的边现在连接到 C*
。
我不清楚如何使用邻接列表等表示来实现此类算法原语。
什么是一种优雅而有效的方式来表示图形,以便它们可以收缩,同时记住相关数据以展开它们?
最佳答案
我会使用 disjoint-set 数据结构也称为联合查找 数据结构。最初将每个顶点想象成一个集合。现在的工作是这样的:
对于收缩:取参与所有收缩的所有顶点的并集。集合中的所有顶点都由称为所有顶点的父节点的单个顶点表示,您可以将其称为 super 节点。该链接包含有关如何执行此操作的所有详细信息。
对于 expansion 只需执行相反的操作,在最坏的情况下,您必须使每个顶点代表一个集合。所以基本上这种方法适用于非重叠集合操作。
关于algorithm - 如何实现需要有效收缩和扩展连接组件的图形算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49597647/