最小生成树 (Prim)

算法

最小生成树是一个连通加权无向图中一棵权值最小的生成树。Prim算法是基于贪心策略来构建最小生成树的经典算法。

时间复杂度:最差 O(V² + E)
空间复杂度:O(V)

应用场景/前提条件

  • 无向加权图
  • 图必须是连通的

算法讲解

最小生成树

介绍

建议学习本节之前,先学习数据结构中的图结构

最小生成树(Minimum Spanning Tree,MST)是图论中的经典问题,它是一个无环连通子图,包含原图中的所有顶点,且边的权重和最小。最小生成树在网络设计、电路布局和聚类算法等领域有广泛应用。

在解决最小生成树问题时,贪心算法是最常用的方法。两种经典的贪心算法是Kruskal算法和Prim算法,这两种算法都能在多项式时间内找到最小生成树。具体内容直接参考 https://algo.codefather.cn/algorithms/graph/prim 和 https://algo.codefather.cn/algorithms/graph/kruskal 即可。

...