Prim最小生成树算法

图算法

Prim算法是一种贪心算法,用于寻找加权无向图的最小生成树,它从单个顶点开始,不断添加权重最小的边来扩展树。

时间复杂度:最佳 O(V² + E) | 平均 O(V² + E) | 最差 O(V² + E)
空间复杂度:O(V)
图类型:加权图

应用场景/前提条件

  • 只适用于连通的无向加权图

算法讲解

Prim最小生成树算法

介绍

Prim算法是一种贪心算法,一般用于在无向连通加权图中寻找最小生成树。最小生成树是一个包含图中所有顶点的无环连通子图,且所有边的权重总和最小。Prim算法的核心思想是从一个起始顶点开始,不断选择与当前树连接的最小权重边,逐步构建最小生成树,直到包含所有顶点。

算法步骤

  1. 选择图中任意一个顶点作为起始点,加入最小生成树集合
  2. 初始化一个优先队列,包含所有与当前最小生成树集合中顶点相邻的边
  3. 从优先队列中选择权重最小的边,如果该边连接的顶点已在最小生成树集合中,则丢弃;否则将该顶点加入最小生成树集合
  4. 更新优先队列,加入与新顶点相邻的边
  5. 重复步骤3和4,直到最小生成树包含图中所有顶点或优先队列为空

算法详解

假设有一个包含5个顶点(A-E)的无向连通加权图,边的关系及权重如下:

  • A与B相邻,权重为2
  • A与C相邻,权重为3
  • B与C相邻,权重为1
  • B与D相邻,权重为4
  • C与D相邻,权重为5
  • C与E相邻,权重为6

...