Kruskal 的算法

Kruskal 算法是一种贪心算法,用于查找图的最小生成树(MST) 。最小生成树是连接图的所有顶点并具有最小总边权重的树。

Kruskal 的算法是通过重复挑选具有最小权重的边 (它们尚未在 MST 中)来实现的,如果由该边连接的两个顶点尚未在 MST 中连接,则将它们添加到最终结果中,否则它会跳过该边。联合 - 查找数据结构可用于检查 MST 中是否已连接两个顶点。MST 的一些属性如下:

  1. 具有 n 顶点的图形的 MST 将具有正好的 n-1 边缘。
  2. 从每个顶点到每个其他顶点存在唯一的路径。