Prim的算法修改

Question

G =（V，E）和A⊆E我一直想知道如何获得最小生成树，如果它需要包含A中的所有边（并且仍然必须具有最小权重），通过修改Prim的算法。

有人可能会给我一些有关如何有效修改算法的提示/想法吗？

Answer 1

使用A中的边将阻止您获得实际的最小生成树，除非A中的边缘保证属于MST。

但是，给定一个A集合，您可以找到将所有其他顶点连接到A的MST。

您没有表明保证A中的边形成单个连接组件，因此我假设它们没有。

在这种情况下，使用Prim的算法是一个坏主意，因为Prim的算法假定在每一步中您在有效MST和不在MST中的点之间添加边。由于A形成的“MST”可能是非连续的，这打破了Prim算法的假设。

相反，使用Kruskal's algorithm。它通过按照长度的顺序考虑边缘来为“MST集”添加边，始终首先选择最短边。如果边缘的两端已经在MST集中，则拒绝边缘。如果MST集中只有一个边，则新边将添加到MST集。

您可以像这样实现算法：

KRUSKAL(G,A):
  mst_set = ∅
  for each vertex v ∈ G.V:
    MAKE-SET(v)
  for each edge (u,v) in A:
    mst_set = mst_set ∪ {(u,v)}
    UNION(u,v)
  for each edge (u, v) in G.Edges ordered by weight(u, v), increasing:
    if FIND-SET(u) ≠ FIND-SET(v):
      mst_set = mst_set ∪ {(u, v)}
      UNION(u, v)
  return mst_set

其中MAKE-SET，UNION和FIND-SET操作是不相交数据结构的一部分。