如果某些边缘是固定的，那么用于 MST 的标准 Kruskal 类方法是否可行？
Will a standard Kruskal-like approach for MST work if some edges are fixed?
问题：你需要找到图的最小生成树（即所述图中边的集合 S，使得 S 中的边与各自的顶点一起形成一棵树；此外，从所有这些集合中，S 中所有边的成本之和必须是最小的）。但有一个陷阱。给定一组初始固定边 K，使得 K 必须包含在 S 中。
换句话说，找到包含一组起始固定边的图的一些 MST。
我的方法：标准 Kruskal 算法，但在其他任何事情之前加入固定边集指向的所有顶点。也就是说，如果 K = {1,2}, {4,5} 我应用 Kruskal 算法，但最初不是让每个节点都在其自己的单独集合中，而是节点 1 和 2 在同一集合中，节点 4 和 5 在同一集合中。
问题：这行得通吗？是否有证据表明这总是会产生正确的结果？如果不是，谁能提供一个反例？
P.S。问题只询问找到ONE MST。对它们都不感兴趣。
如果我正确理解了这个问题，Prim's algorithm 会更适合这个问题，因为可以将连接的组件初始化为生成的生成树中需要出现的边（加上剩余的孤立节点）。所需的边不允许包含循环，否则没有包含它们的生成树。
话虽这么说，显然也可以使用 Kruskal's algorithm，因为明确指出它可以用于找到以 cost-minimal 方式连接两个森林的边。
粗略地说，当给定图的森林形成一个 Matroid, the greedy approach yields the desired result (namely a weight-minimal tree) regardless of the independent set 开始时。
是的，只要您的初始边集不形成循环，它就可以工作。
请记住，生成的树的权重可能不是最小的，因为您修复的边可能不是图中任何 MST 的一部分。但是你会得到最轻的生成树，它满足那些固定边是树的一部分的约束。
实现方式：
要实现这一点，您只需更改需要修复的边的 edge-weights。只需选择图表中出现的最低 edge-weight，比如 min_w，从中减去 1 并分配这个新权重，即(min_w-1) 到您需要修复的边缘。然后 运行 Kruskal 在这张图上。
为什么有效：
显然，Kruskal 会先选择您需要的所有边（因为这些边现在最轻），然后再选择图中的任何其他边。当 Kruskal 完成时，生成的一组边是 G' 中的 MST（您更改了一些权重的图）。请注意，由于您只更改了固定边集的值，因此算法永远不会在其他边（不属于固定边集的边）上做出不同的选择。如果您将 Kruskal 考虑的边视为边的排序列表，那么更改需要修复的边的值会将这些边移动到列表的前面，但不会更改其他边的顺序列表相对于彼此。
注意：正如您可能注意到的，给边缘赋予最轻的重量与您建议的基本相同。但我认为更容易理解它为什么起作用。随心所欲。
我不推荐Prim，因为这个算法是从当前连接的组件开始逐渐扩展生成树的（一开始通常从一个节点开始）。如果您加入较大的组件（因为您的固定边缘可能不在一个组件中），则需要单独处理 - 这可能不难，但您必须处理它。 OTOH 使用 Kruskal，您无需进行任何调整，只需在 运行 使用常规算法之前稍微操作一下图形即可。
问题：你需要找到图的最小生成树（即所述图中边的集合 S，使得 S 中的边与各自的顶点一起形成一棵树；此外，从所有这些集合中，S 中所有边的成本之和必须是最小的）。但有一个陷阱。给定一组初始固定边 K，使得 K 必须包含在 S 中。
换句话说，找到包含一组起始固定边的图的一些 MST。
我的方法：标准 Kruskal 算法，但在其他任何事情之前加入固定边集指向的所有顶点。也就是说，如果 K = {1,2}, {4,5} 我应用 Kruskal 算法，但最初不是让每个节点都在其自己的单独集合中，而是节点 1 和 2 在同一集合中，节点 4 和 5 在同一集合中。
问题：这行得通吗？是否有证据表明这总是会产生正确的结果？如果不是，谁能提供一个反例？
P.S。问题只询问找到ONE MST。对它们都不感兴趣。
如果我正确理解了这个问题，Prim's algorithm 会更适合这个问题，因为可以将连接的组件初始化为生成的生成树中需要出现的边（加上剩余的孤立节点）。所需的边不允许包含循环，否则没有包含它们的生成树。
话虽这么说，显然也可以使用 Kruskal's algorithm，因为明确指出它可以用于找到以 cost-minimal 方式连接两个森林的边。
粗略地说，当给定图的森林形成一个 Matroid, the greedy approach yields the desired result (namely a weight-minimal tree) regardless of the independent set 开始时。
是的，只要您的初始边集不形成循环，它就可以工作。
请记住，生成的树的权重可能不是最小的，因为您修复的边可能不是图中任何 MST 的一部分。但是你会得到最轻的生成树，它满足那些固定边是树的一部分的约束。
实现方式：
要实现这一点，您只需更改需要修复的边的 edge-weights。只需选择图表中出现的最低 edge-weight，比如 min_w，从中减去 1 并分配这个新权重，即(min_w-1) 到您需要修复的边缘。然后 运行 Kruskal 在这张图上。
为什么有效：
显然，Kruskal 会先选择您需要的所有边（因为这些边现在最轻），然后再选择图中的任何其他边。当 Kruskal 完成时，生成的一组边是 G' 中的 MST（您更改了一些权重的图）。请注意，由于您只更改了固定边集的值，因此算法永远不会在其他边（不属于固定边集的边）上做出不同的选择。如果您将 Kruskal 考虑的边视为边的排序列表，那么更改需要修复的边的值会将这些边移动到列表的前面，但不会更改其他边的顺序列表相对于彼此。
注意：正如您可能注意到的，给边缘赋予最轻的重量与您建议的基本相同。但我认为更容易理解它为什么起作用。随心所欲。
我不推荐Prim，因为这个算法是从当前连接的组件开始逐渐扩展生成树的（一开始通常从一个节点开始）。如果您加入较大的组件（因为您的固定边缘可能不在一个组件中），则需要单独处理 - 这可能不难，但您必须处理它。 OTOH 使用 Kruskal，您无需进行任何调整，只需在 运行 使用常规算法之前稍微操作一下图形即可。