算法与数据结构学习（55）-程序员常用10种算法（普利姆算法）

普利姆算法应用场景

问题转化

最小生成树
修路问题本质就是就是最小生成树问题， 先介绍一下最小生成树(Minimum Cost Spanning Tree)，简称MST。

1. 给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树
   2.N个顶点，一定有N-1条边
2. 包含全部顶点
3. N-1条边都在图中
4. 举例说明(如图:)
5. 求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法
   

普利姆算法介绍

1. 从< A >点开始分析处理 ====><A,G>
   A-C[7] A-B[5] A-G[2]
2. 从<A，G>开始，将A和G顶点和他们的相邻的还没有访问的顶点进行处理 ====><A,G,B>
   A-C[7] A-B[5] G-B[3] G-E[4] G-F[6]
3. 从<A,G,B>开始，将顶点A，G，B和他们的相邻的还没有访问的顶点进行处理 ====><A,G,B,E>
   A-C[7] G-E[4] G-F[6] B-D[9]
4. 以此类推
5. 最后得到完整集合<A,G,B,E,F,D,C>