最小生成树（MinimumSpanningTree）简称MST，是图论中的概念，通常用来计算连通图中的最短路径，是一种常见的路径优化方法。最小生成树看起来跟机器学习八竿子打不着，在各种参考书里也找不到任何关于它的描述。其实机器学习的目的从本质上来讲就是分类和优化，从这一点来看，两者还是有交叉的地方，将最小生成树引入到机器学习当中往往能起到意想不到的效果。
下面通过一个例子来一下什么是最小生成树。假设要在7个城市之间铺设通信光缆，不同的城市之间铺设光缆的代价各不相同，如何选择最佳铺设方案，在保证7个城市间能正常通信的基础上，使总花费最低？上图用字母A~G代表不同的城市，数字表示两个城市之间的铺设成本。上图中的绿色连线是计算得出的最佳方案，这种树形结构就是该问题的最小生成树。
Prim算法
寻找最小生成树的算法有很多，这里介绍最基础的Prim算法。该算法是通过反复地增加边来建立一棵树直到得到一个最小生成树。核心思想是建立两个集合mst和left，分别用于保存最小生成树节点和剩余节点，每次迭代从两个集合中各取一个节点，遍历所有可能组合的边的长度，将最短边对应的节点添加到集合mst中，直到集合left中节点的个数为0。Prim算法的步骤如下：
数据初始化：最小生成树节点集合mst={0}，剩余节点集合left={1,2,3,4,5,6}，边集合为空集；判断left是否为空，如果为空跳转第6步，如果不为空继续执行；双重for循环遍历mst和left，用表示节点P与的边长（P，分别是mst和left中的节点），寻找边长的最小值min()；将最小值对应的加入mst，同时将从left中移除，并将边的信息存入（包括两个节点和边的长度）；跳转到第2步；打印集合mst和边的集合。为了描述方便，我们在第1步数据初始化时，将节点0放入集合mst中，实际上，无论我们在第1步将哪个节点放入mst，都不会影响最后的结果。读者也可以修改下文的python代码自行验证。
python实现
在初始化的过程中非常重要的一步就是构建边长矩阵，本文的例子中共有7个节点，矩阵大小应该为7×7，该矩阵是一个主对角线元素为0的对称阵，第i行第j列的元素表示节点i与节点j之间的边长，如果两个节点之间没有边连接，则取值为-1。
核心代码如下图所示，逻辑结构很清楚，代码也非常简单。使用while循环判断结束条件；里面嵌套了双重for循环对mst_nodes和left_nodes进行遍历；寻找最小边，更新集合；最后打印出结果。代码在理解上没有任何难度，这里不再赘述。代码的获取方式见上图。