求最小生成树的Prim算法

Prim算法最开始把所有的节点每个节点作为一个树,所有的节点成为森林,最开始从第一个节点开始作为最小生成树一部分A,依次向所有的节点扩展,每次找离最小生成树最小的一个顶点,直到所有的顶点添加到最小生成树里,即形成了一个最小生成树。
step 0 :选择任意元素r,集合S={r},A=空,r即为最小生成树的根
step 1 :找到一个权重最小的边,一个点在S 一个在V\S 把这个边添加到A 这个顶点添加到S
step 2 : 如果V\S为空 结束 输出最小生成树
不为空 重复step1
求最小生成树的Prim算法
求最小生成树的Prim算法
求最小生成树的Prim算法
求最小生成树的Prim算法
求最小生成树的Prim算法
更新S时使用color[v],即最开始时,所有的color均为WHITE,当把顶点加入S时,color变为BLACK
使用优先队列来更新A,使用最小堆来实现优先队列
伪代码:
求最小生成树的Prim算法求最小生成树的Prim算法
求最小生成树的Prim算法

求最小生成树的Prim算法