问题:您需要找到图的最小生成树(即所述图中边的集合 S，使得 S 中的边与各自的顶点一起形成一棵树；此外，从所有这些集合中， S 中所有边的成本总和必须是最小的)。但有一个陷阱。给定一组初始的固定边 K，使得 K 必须包含在 S 中。
换句话说，找到包含一组起始固定边的图的一些 MST。
我的方法:标准 Kruskal 算法，但在执行任何其他操作之前，连接固定边集指向的所有顶点。也就是说，如果 K = {1,2}, {4,5} 我应用 Kruskal 算法，但不是让每个节点最初都在其自己的单独集合中，而是节点 1 和 2 在同一个集合中set 和节点 4 和 5 在同一个集合中。
问题:这行得通吗？是否有证据表明这总是会产生正确的结果？如果不是，谁能提供一个反例？
附言问题只询问找到ONE MST。对所有这些都不感兴趣。
最佳答案
是的，只要您的初始边集不形成循环，它就可以工作。
请记住，生成的树的权重可能不是最小的，因为您修复的边可能不是图中任何 MST 的一部分。但是你会得到最轻的生成树，它满足那些固定边是树的一部分的约束。
如何实现:
要实现这一点，您只需更改需要修复的边的边权重即可。只需选择图中出现的最低边缘权重，比如 min_w，从中减去 1 并分配这个新权重，即(min_w-1) 到您需要修复的边缘。然后在此图上运行 Kruskal。
为什么有效:
显然，Kruskal 会先选择您需要的所有边(因为这些边现在最轻)，然后再选择图中的任何其他边。当 Kruskal 完成时，生成的一组边是 G' 中的 MST(您更改了一些权重的图)。请注意，由于您只更改了固定边集的值，因此算法永远不会在其他边(不属于固定边集的边)上做出不同的选择。如果您将 Kruskal 考虑的边视为边的排序列表，那么更改需要修复的边的值会将这些边移动到列表的前面，但不会更改其他边的顺序列表相对于彼此。
注意:您可能会注意到，为边缘赋予最轻的重量与您建议的基本相同。但我认为更容易理解它为什么起作用。随心所欲。
我不推荐 Prim，因为该算法从当前连接的组件逐渐扩展生成树(一开始通常从单个节点开始)。如果您加入较大的组件(因为您的固定边缘可能不在一个组件中)，则需要单独处理 - 这可能不难，但您必须处理它。 OTOH 使用 Kruskal，您无需进行任何调整，只需在运行常规算法之前稍微操作一下图形即可。
关于algorithm - 如果某些边缘是固定的，那么用于 MST 的标准 Kruskal 类方法是否可行？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42205727/