graph - 简化/减少图的算法

Question

是否有基于边缘成本缩短路径（并删除节点）的算法？我不能很好地用语言表达，所以我希望这些图像能够很好地总结出来：

标签： graphgraph-theorygraph-algorithmgraph-reduction

Answer 1

您是在寻找开箱即用的东西，还是在寻找关于如何自己实现它的算法想法？后者我可以帮你。

您想要做的是称为具有完全邻居的顶点的收缩2，即具有 degree 2。

为了实现这一点，请执行以下操作：

while exists vertex v with degree 2:
    - remove v and the 2 outgoing edges
    - add a new edge between the neighbours of v
    - the weight of the new edge is the sum of the weights of the deleted edge

也就是说，如果您有图表的以下部分： u ---2--- v ---5--- w并应用收缩，您最终会得到u ---7--- w.

只需迭代地执行此操作，直到没有保留度数的顶点即可2将第一张图片中的图形转换为第二张图片中的图形。

当然，确切的实现细节将取决于您使用哪种数据结构来表示 Python（或任何其他正在使用的语言）中的图形。