algorithm - 如何找到包含给定边的最小生成树？

Question

在加权无向图中，如果可能的话，我需要找到包含给定边“e”的最小生成树。我该怎么做？ Kruskal 从 'e' 开始？

Answer 1

我不会使用Kruskal算法，因为如果边e是循环的一部分并且e在该循环中具有最大权重，则该算法将不包括'e'。我相信通过修改它可以工作。但是使用 Prim 的算法所需的修改是最小的。

Prim 的算法最适合这个问题，如果我们记忆一下 Prim 算法是这样的:

第 1 步:从包含随机选取的顶点的集合 S 开始。

第 2 步:从具有集合 S 中的一个顶点和集合 V 中的其他顶点的所有边 - S，选择权重最小的那一个。设(x,y)，x属于S，y属于V - S。

第 3 步:添加y 以设置S。

第 4 步:重复第 2 步和第 3 步，直到 S 包含所有顶点。

需要修改:

对于您的问题，只需将步骤 1 更改为:

第 1 步:从包含顶点 u 和 v 的集合 S 开始，其中边 ' e' = (u,v).