最短路径之prime算法
2021-03-08 17:31
标签：复杂度 ++ 时间 顶点 include 递归 ret 生成 初始 prime算法与dijkstra算法非常相似，主要区别是更新连接路径时，prime中是跟踪接下来的结点到生成树中的最小交叉边，而dijkstra中是跟踪接下来的结点到 算法描述： 普利姆算法求最小生成树时候，和边数无关，只和定点的数量相关，所以适合求稠密网的最小生成树，时间复杂度为O（n*n）。 算法实现具体过程： 最短路径之prime算法 标签：复杂度 ++ 时间 顶点 include 递归 ret 生成 初始 原文地址：https://www.cnblogs.com/tzp-empty-hya/p/14195094.html
起点所有经过的结点的路径和，这个算法也能算出花最少的钱去把各个村庄连接起来。
算法过程：
1.将一个图的顶点分为两部分主要，一部分是最小生成树中的结点（A集合），另一部分是未处理的结点（B集合）。
2.首先选择一个结点，将这个结点加入A中，然后，对集合A中的顶点遍历，找出A中顶点关联的边权值最小的那个（设为v），将此顶点从B中删除，加入集合A中。
3.递归重复步骤2，直到B集合中的结点为空，结束此过程。
4.A集合中的结点就是由Prime算法得到的最小生成树的结点，依照步骤2的结点连接这些顶点，得到的就是这个图的最小生成树。
1.将第一个点放入最小生成树的集合中。
2.从第二个点开始，初始化为跟1点相连（仅仅相连）的边的权值）。
3.找最小权值的边。
从第二点开始遍历，如果不是最小生成树的集合的点，则找出从2到n的最小权值）。
4.将找出来的最小权值的边的顶点加入最小生成树的集合中，权值相加。
5.更新集合。
6.循环上述步骤，指导将全部顶点加入到最小生成树集合为止。include
#include
上一篇：java->方法及数组