最小生成树-Prim(普里姆)算法解析

prim算法是无向加权图寻找最小生成树的算法，简单理解他的寻找路径的过程，从一个顶点V0开始，首先找到所有与V0相关联的顶点，查看这些顶点到V0的加权值，找出最小的一个，然后将该顶点纳入已统计顶点中。寻找第三个顶点时，将V0、之前已算出的顶点与所有相关联且未统计的顶点，找出最小的一个，纳入已统计顶点中。后面的寻顶点规则同上所述。最后找出最小的生产树路径。
如下图：从任意顶点开始都可以，这里从V0开始为例子

（1）与V0关联的有V1、V2、V3；由V0V1=9,V0V2=8,V0V3=13,得出V0V2最小，所以选出顶点V0、V2；
（2）此时所有与V0、V2关联的节点且未选出的节点有V1、V3、V5；V0V1=9,V0V3=13,V2V3=11,V2V5=12,得出V0V1=9最小，选出顶点V0、V2、V1;
（3）此时所有与V0、V2、V1关联的节点且未选出的节点有V4、V3、V5；同上所述得出V1V4=7最小，选出顶点V0、V2、V1、V4;
（4）此时所有与V0、V2、V1、V4关联的节点且未选出的节点有V6、V3、V5；同上所述得出V3V4=5最小，选出顶点V0、V2、V1、V4、V3;
（5）此时所有与V0、V2、V1、V4、V3关联的节点且未选出的节点有V6、V7、V5；同上所述得出V3V6=8最小，选出顶点V0、V2、V1、V4、V3、V6;
（6）此时所有与V0、V2、V1、V4、V3、V6关联的节点且未选出的节点有V7、V5；同上所述得出V3V7=10最小，选出顶点V0、V2、V1、V4、V3、V6、V7;
（7）此时所有与V0、V2、V1、V4、V3、V6、V7关联的节点且未选出的节点有V5；同上所述得出V5V7=6最小，选出顶点V0、V2、V1、V4、V3、V6、V7、V5;
最终生成的最小生成树如下图红色边连接的顶点构成的树，计算总权值为8+9+7+5+8+10+6=53

从上面的遍历可以得知需要进行两层循环遍历，所以时间复杂度为O(n^2)