prim算法——-典型的贪心算法

求最小生成树的算法

（Minimum Spanning Tree）最小生成树：

算法思想：设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一颗MST。

算法用途（解决的问题）：最实际的n个村庄然后建路，只要实现连通就行。求造完的最短路。

算法注意（流程）：

1. 初始化；

2. 循环n-1次，取点，更新；

3. For一遍dist，得出ans；

实现算法（代码加注释）：

类似算法（相同以及差异【另开专题】）：Kruskal算法