Prim最小生成树算法
介绍
Prim算法是一种贪心算法,一般用于在无向连通加权图中寻找最小生成树。最小生成树是一个包含图中所有顶点的无环连通子图,且所有边的权重总和最小。Prim算法的核心思想是从一个起始顶点开始,不断选择与当前树连接的最小权重边,逐步构建最小生成树,直到包含所有顶点。
算法步骤
- 选择图中任意一个顶点作为起始点,加入最小生成树集合
- 初始化一个优先队列,包含所有与当前最小生成树集合中顶点相邻的边
- 从优先队列中选择权重最小的边,如果该边连接的顶点已在最小生成树集合中,则丢弃;否则将该顶点加入最小生成树集合
- 更新优先队列,加入与新顶点相邻的边
- 重复步骤3和4,直到最小生成树包含图中所有顶点或优先队列为空
算法详解
假设有一个包含5个顶点(A-E)的无向连通加权图,边的关系及权重如下:
- A与B相邻,权重为2
- A与C相邻,权重为3
- B与C相邻,权重为1
- B与D相邻,权重为4
- C与D相邻,权重为5
- C与E相邻,权重为6
...