最小生成树(MST)删除额外边拆分的最优删除顺序求解

核心等价转化 #

你描述的问题本质可以做如下简化：
额外边的本质就是图中存在环时的冗余边，删除所有额外边后图必然是无环的森林结构。你的目标是删除的额外边总权重最小，等价于保留下来的边总权重最大，因为图中所有边的总权重是固定值，删除权重 = 总权重 - 保留权重。

最优解法（Kruskal 最大生成树法） #

直接用最大生成树的构造逻辑即可得到最优解，步骤如下：

• 将图中所有边按权重从大到小排序
• 初始化并查集结构，每个顶点单独作为一个连通块
• 按权重从高到低遍历所有边：
  • 如果当前边的两个顶点不在同一个连通块，保留这条边，合并两个顶点的连通块
  • 如果两个顶点已经连通，这条边就是需要删除的额外边，计入删除总权重
• 遍历完成后得到的删除总权重就是最小值

原思路错误原因 #

你最初优先删除最大权重额外边的思路刚好和最优目标相反：删除权重高的边会直接导致保留的总权重下降，反而会拉高删除总权重。最优逻辑是优先保留权重高的边，只删除会导致环出现的、权重更低的边。

内容的提问来源于stack exchange，提问作者Python Newbie