我正在学习MST算法。我很想找到prims和boruvka算法之间的关键区别，但网上的资源除了它们的实现和算法之外，没有太多关于它们的内容。如果有人能解释，那将是一个很大的帮助。谢谢
两种算法都使用
-
对于每个顶点v，存在一个最小生成树T，使得入射到v的最便宜的边属于T。
-
对于每条边e，包含e的(最小(生成树与收缩e的图的(最小的(生成树自然一一对应。
Prim和Borůvka以不同的方式利用这些事实。Prim选择一个根顶点r，并重复地将最便宜的边收缩到r(通常的描述避免了图收缩，但与此等价(，直到只剩下r。Borůvka反复收缩所有最便宜的事件边缘"并行地"；直到刚好剩下一个顶点。
您可以通过混合和匹配收缩策略来创建各种最小生成树算法。