最小生成树构造-prim算法
普里姆（Prim）算法是一种用于构造最小生成树的算法。它通过每次添加一个新节点加入集合，直到所有点加入停止，来保证生成树的边权总和最小。
1. 初始化：将起点的邻接矩阵录入cost中，将所有加点位置（adjvex）置为起点。
2. 从起点开始对剩余的(n-1)个点迭代：每轮迭代过程中，首先需要在cost数组内寻找最小值，并输出本轮最小值到上一轮最小值之间的代价，同时将本轮最小值位置的数据清0，以防止之后的遍历重复。之后再次找最小权值，并更新cost数组，同时在adj数组中记录上一轮迭代得到最小值的位置。
3. 重复以上操作n-1次，最小生成树的代价就是连接的所有边的权值之和。
需要注意的是，Prim算法最适合用于稠密图的算法。
如有侵权请及时联系我们处理，转载请注明出处来自
推荐文章
科技快看 网站地图广州壹创集信息科技有限公司 版权所有 粤ICP备2021122624号
