最小的横跨树用于将所有节点用一个图与最小的总边重连接起来。 找到这些树的两个常见算法是克鲁斯卡尔和普里姆的算法。 这两个算法都是高效的,但在方法和执行上有所不同。

克鲁斯卡尔的算法

Kruskal 的算法按重量排序图中的所有边缘。然后它会从最小处开始,在横跨树上添加边缘,确保不形成循环。这一过程将持续到所有节点连接起来。

该算法对稀疏的图表特别有效,它使用脱节的集数据结构来高效地检查添加边值是否会创建一个周期.

普林的算法

Prim的算法从任意节点开始,通过将连接树的最小边缘添加到新节点来生长横断树。它一直持续到包含所有节点。

这种方法通常为密集的图表所偏好,它使用优先排队的方式,以高效的最小重量选择下一个边缘.

比较和执行

两种算法都保证找到最小跨树,但其效率取决于图的结构。 Kruskal 的比较简单,可以集中进行边缘排序,而Prim 的则可以使用优先排队的密集图来提高效率。

  • 克鲁斯卡尔在全球的优势
  • Prim 将树从起点点生长出来
  • 两者都使用不同的数据结构提高效率
  • 选择取决于图密度和大小