什么是最小生成树
最小生成树（Minimum Spanning Tree ）简称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进行遍历；寻找最小边，更新集合；最后打印出结果。代码在理解上没有任何难度，这里不再赘述。代码的 获取方式见上图。
总结
贪心算法的特点就是在不考虑前面所选择的情况下，使在每次迭代中的选择达到最优，得到的往往是“局部最优解”。Prim算法其实是贪心算法的一个例子，因此Prim算法可能无法得到最优解。求最小生成树还有其它算法，我将在接下来的文章里为大家介绍，敬请期待。
到此这篇prim算法（prim算法思想）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/rfx/40573.html