普里姆算法 | 动画算法与数据结构

符号

数据
连接 T 中节点的边的权重最小值 dist
在最小生成树中的父节点 parent
节点之间的距离 weight

起点的确定和初始化
选择任意节点作为起点,将其初始化为 0
将其他节点的 dist 初始化为大值
最小生成树的构建
寻找 dist 最小的节点 # find minimum
指向权重最小的节点 u
更新节点的 dist 和 parent dist[v] ← weight[u][v]
parent[v] ← u
表示最小生成树的临时边 (v, parent[v])
扩展最小生成树的范围 将 u 加入 T
最小生成树的输出
从父节点信息开始构建最小生成树

动画

起点的确定和初始化
普里姆算法 | 起点的确定和初始化

最小生成树的构建
普里姆算法 | 最小生成树的构建

最小生成树的输出
普里姆算法 | 最小生成树的输出