如何构造含恰好N条跨河边的最小生成树（MST）？

核心步骤 #

• 第一步：分别计算两个原图的最小生成树（MST1对应左图，MST2对应右图）。这一步确保两个图内部的连接权重已经是最小的，为后续合并打下基础。
• 第二步：从所有可选跨河边中选出权重最小的N条，记为E_cross。
• 第三步：将MST1、MST2与E_cross合并成一个图。此时这个图大概率存在环——因为多条跨河边连接的顶点在各自的MST中是连通的，跨河边+MST内部路径会形成闭合环。
• 第四步：对每个新增的跨河边（即第2到第N条），找到它在合并图中形成的环，移除环中权重最大的非跨河边。这样操作后，既能保留所有N条跨河边，又能消除环，最终得到的图就是连通无环的MST，且总权重最小。

思路验证与答疑 #

• 针对「修改Prim算法强制选指定边」的思路：这种方式确实可能引入环，但如果在选边后同步处理环（移除环内最大权重的非指定边），本质和上述步骤一致。不过直接先生成两个独立MST再合并调整，逻辑更清晰，实现起来也更简单。
• 针对「先求左右MST再用跨河边连接，移除环中最大权重边」的思路：这个方向是对的，但要注意必须移除环内权重最大的非跨河边——因为我们的目标是保留N条跨河边，不能把跨河边当成环里的最大边移除，否则就达不到N条的要求。

示例场景适配 #

拿题目中的例子来说：左图顶点(0,1,2,3)，右图顶点(4,5,6,7,8)，可选跨河边为3-4、3-5、2-4、2-5，N=2。

1. 先算出左图的MST1和右图的MST2；
2. 选出两条权重最小的跨河边（比如假设是3-4和2-5）；
3. 合并后会形成环：3-4（跨河）→ 4在MST2中的路径→5→2-5（跨河）→2在MST1中的路径→3；
4. 找到这个环里权重最大的内部边（来自MST1或MST2）并移除，最终就得到了恰好包含2条跨河边的MST，也就是示例中的红色部分。

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