图的简化/约简算法

你想做的事叫做 contraction 顶点的 2 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(或正在使用的任何其他语言)表示图形的数据结构。