在学习Prim算法，也就是普利姆算法前，要先对图有一定的了解，具体的可以看看小编以前分享的一些相关文章。今天，小编就通过图解的方法来阐述下该最小生成树算法，并贴上相关代码。
我们来看一个例子，如下图所示，G是一个连通图：
连通图G
我们基于该图来演示Prim算法。
我们设置顶点集合为V，U为已选中顶点集合。
为了便于选中当前权值最小的边的节点，需要建立两个数组closest和lowcost，这两个关键的数据结构这里要解释清楚下：
（1）lowcost[i]：表示以i为终点的边的最小权值,当lowcost[i]=0说明以i为终点的边的最小权值=0,也就是表示i点加入了MST（最小生成树）。
（2）closest[i]：表示对应lowcost[i]的起点，即说明边<closest[i],i>是MST的一条边，当closest[i]=0表示起点i加入MST。
可能这么来讲有点不太好理解，那接下来我们直接来一步步分析。
我们取顶点V1为起始点【这里顶点V1，V2，V3，V4，V5，V6在顶点表对应位置分别为0，1，2，3，4，5】，INF代表无穷大。
当前起始点在顶点表位置为0，那么有：
U={V1}；
closest[0]=0，closest[1]=0，closest[2]=0，closest[3]=0，closest[4]=0，closest[5]=0；
其它顶点与该顶点有木有边，权重如何，我们通过lowcost数组反映出来：
lowcost[0]=0，lowcost[1]=6，lowcost[2]=1，lowcost[3]=5，lowcost[4]=INF，lowcost[5]=INF；
其中，lowcost[0]=0表示顶点V1到自己的距离为0，lowcost[1]=6表示顶点V1到V2距离为6，依此类推。
从上述lowcost数组可以发现，lowcost[2]=1最小，也就是说以V3为终点的边的权值最小，所以将边<V1,V3>加入最小生成树，也就是<closest[2],2>【顶点所处位置】，设置lowcost[2]=0，代表该顶点V3已加入MST，也意味该点被选过，下次不再进行选择。得到下图：
过程1
因为V3的加入，此时需要对这两个数组进行更新：
因为<V1,V2>=6，<V3,V2>=5，5<6因此更新lowcost[1]=5，closest[1]=2；
因为<V1,V4>=5，<V3,V4>=5，不更新lowcost[3]和closest[3]，因此此时lowcost[3]=5，closest[3]=0；
因为<V1,V5>=INF，<V3,V5>=6，因此更新lowcost[4]=6，closest[4]=2；
因为<V1,V6>=INF，<V3,V6>=4，因此更新lowcost[5]=4，closest[5]=2；
此时：U={V1，V3}；
得到新的数组如下：
lowcost[0]=0，lowcost[1]=5，lowcost[2]=0，lowcost[3]=5，lowcost[4]=6，lowcost[5]=4；
closest[0]=0，closest[1]=2，closest[2]=0，closest[3]=0，closest[4]=2，closest[5]=2；
从上述lowcost数组可以发现，lowcost[5]=4最小，也就是说以V6为终点的边的权值最小，所以将边<V3,V6>加入最小生成树，也就是<closest[5],5>【顶点所处位置】，设置lowcost[5]=0，代表给顶点已被选过，下次不再进行选择。得到下图：
过程2
因为V6的加入，此时需要对这两个数组进行更新：
因为<V3,V2>=5，<V6,V2>=INF，不更新lowcost[1]和closest[1]，因此此时lowcost[1]=5，closest[1]=2；
因为<V3,V4>=5，<V6,V4>=2，2<5，因此更新lowcost[3]=2，closest[3]=5；
因为<V3,V5>=6，<V6,V5>=6，不更新lowcost[4]和closest[4]，因此此时lowcost[4]=6，closest[4]=2；
此时：U={V1，V3，V6}；
得到新的数组如下：
lowcost[0]=0，lowcost[1]=5，lowcost[2]=0，lowcost[3]=2，lowcost[4]=6，lowcost[5]=0；
closest[0]=0，closest[1]=2，closest[2]=0，closest[3]=5，closest[4]=2，closest[5]=2；
从上述lowcost数组可以发现，lowcost[3]=2最小，也就是说以V4为终点的边的权值最小，所以将边<V6,V4>加入最小生成树，也就是<closest[3],3>【顶点所处位置】，设置lowcost[3]=0，代表给顶点已被选过，下次不再进行选择。得到下图：
过程3
因为V4的加入，此时需要对这两个数组进行更新：
因为<V4,V2>=INF，<V3,V2>=5，不更新lowcost[1]和closest[1]，因此此时lowcost[1]=5，closest[1]=2；
因为<V4,V5>=INF，<V3,V5>=6，不更新lowcost[4]和closest[4]，因此此时lowcost[4]=6，closest[4]=2；
此时：U={V1，V3，V6，V4}；
得到新的数组如下：
lowcost[0]=0，lowcost[1]=5，lowcost[2]=0，lowcost[3]=0，lowcost[4]=6，lowcost[5]=0；
closest[0]=0，closest[1]=2，closest[2]=0，closest[3]=5，closest[4]=2，closest[5]=2；
从上述lowcost数组可以发现，lowcost[1]=5最小，也就是说以V2为终点的边的权值最小，所以将边<V3,V2>加入最小生成树，也就是<closest[1],1>【顶点所处位置】，设置lowcost[1]=0，代表给顶点已被选过，下次不再进行选择。得到下图：
过程4
因为V2的加入，此时需要对这两个数组进行更新：
因为<V2,V5>=3，<V3,V5>=6，3<6，因此更新lowcost[4]=3，closest[4]=1；
此时：U={V1，V3，V6，V4，V2}；
得到新的数组如下：
lowcost[0]=0，lowcost[1]=0，lowcost[2]=0，lowcost[3]=0，lowcost[4]=3，lowcost[5]=0；
closest[0]=0，closest[1]=2，closest[2]=0，closest[3]=5，closest[4]=1，closest[5]=2；
从上述lowcost数组可以发现，lowcost[4]=3最小，也就是说以V5为终点的边的权值最小，所以将边<V2,V5>加入最小生成树，也就是<closest[4],4>【顶点所处位置】，设置lowcost[4]=0，代表给顶点已被选过，下次不再进行选择。得到下图：
过程5
此时：U={V1，V3，V6，V4，V2，V5}；
到此发现所有点已经访问过，最小生成树MST构建成功。
通过上述可得知最小生成树相关边为<V1,V3>，<V3,V6>，<V6,V4>，<V3,V2>，<V2,V5>。
代码如下：
Prim算法
通过代码可以发现，Prim算法中有两重for循环，所以时间复杂度为O(n^2)，其中n为图的顶点个数【上图中为numVertices】。
从上述算法的流程也可以看出，这个也是一个贪心算法。
因为小编将有关图的算法等都添加到同一份代码，因此后续等小编将有关的算法更新完后，小编会将整份的源代码分享给大家，当然有误的话，请批评指正，感激不尽！
网友评论