最小生成树的 Prim 和 Kruskal 算法

最小生成树（Prim算法和Kruskal算法）

• 1.最小生成树(MST)

  • 2.Prim算法

  • • 2.1执行步骤
    • 2.2核心理念

  • 3.Kruskal算法

  • • 3.1执行步骤
    • 3.2核心理念

1.最小生成树(MST)

• 生成树：由图中所有顶点构成的最小连通子图。

  • 最小生成树(MST)：针对一个具有权重的连通无向图G(V,E)，假设R表示该图的所有生成树构成的集合，若T是R中边权总和最小的生成树，则T被称为G的最小生成树。
  • 特性：
  1. 最小生成树可能并非唯一存在。
  2. 所有最小生成树中边权总和始终一致。
  3. 构成最小生成树的边的数量等于顶点数量减一。
  • 道路规划要求：确保所有区域实现连通，同时使整体建设成本降至最低水平。

2.Pr