符号
| 数据 | ||
|---|---|---|
| 连接 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 | |
| 最小生成树的输出 | ||
| 从父节点信息开始构建最小生成树 | ||
动画
起点的确定和初始化
最小生成树的构建
最小生成树的输出