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