图论（一）最小生成树_最小生成树上面的约束是什么

作者：人工智能uu | 2024-07-13 17:46:44

踩

最小生成树上面的约束是什么

最小生成树有两种算法：这里先不写代码

1：普利姆算法（prim）：初始状态相当于两个篮子A与B，篮子中装的是点vertex，初始化时候A是空的，B是满的

算法描述：

先从B中随机找一个点放到A中，不断从B中找距离A集合最近的一个点放到A中，直到B为空

在这个过程中最近距离对应的边集便能构成一颗最小生成树

所谓B中距离A集合最近的点就是，与A集合中任意点相连的，且彼此距离最近的B集合中的点；

有点类似吸铁石，每次吸一个，有点像层次聚类的思想，只是prim最终需要寻找的是那些最近的边集合；

其实更像传销，不断的拉新人，每次只能是最近距离的人被拉进来。

2：克鲁斯卡尔算法（kruskal）

算法描述：

prim是找集合最近点，克鲁斯卡尔是找最小边加入到新的边集中，但是有约束，就是新的边集中不能有回路，如果有回路就找次近的边

描述的不好，权当自己看看怕忘了，写成代码中主要是考虑集合的问题

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/人工智能uu/article/detail/820801