2

我正在研究 MST 算法。我很想知道 prims 和 boruvka 的算法之间的主要区别，但是网上的资源除了它们的实现和算法之外没有太多要说的。如果有人可以解释，那将是很大的帮助。谢谢！

4

1 回答 1

3

两种算法都使用以下事实

  • 对于每个顶点 v，存在一个最小生成树 T，使得与 v 关联的最便宜的边属于 T。

  • 对于每条边 e，包含 e 的（最小）生成树与 e 收缩的图的（最小）生成树自然一一对应。

Prim 和 Borůvka 以不同的方式利用这些事实。Prim 选择一个根顶点 r 并反复收缩与 r 相关的最便宜的边（通常的描述避免了图收缩，但等效于此）直到只剩下 r。Borůvka 反复“并行”收缩所有最便宜的事件边，直到只剩下一个顶点。

您可以通过混合和匹配收缩策略来创建各种最小生成树算法。

于 2021-07-18T15:59:23.117 回答