大数据算法系列13:最小生成树算法

一. Kruskal算法

二. Prim算法

普里姆（Prim）算法，也是求加权连通图的最小生成树的算法。

基本思想
对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。从所有的 $uЄU$ ，$vЄ(V-U)$（V-U表示除去U的所有顶点）的边中选取权值最小的边（u，v），将顶点v加入U中，将边（u,v）加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，此时集合T中包含了最小生成树中的所有边。

三. Bellman-Ford算法

四. 算法在计算机网络中的应用

计算机网络中，节点非长多，需要访问的资源分布在不同的节点上，怎么在最短的路径上访问到想要的内容，使用的就是最小生成树的算法的思想。

参考:

1. http://www.dataguru.cn/article-5747-1.html