24.最小生成树
一、Kruskal算法
每次选择权值最小的边，若该边两点没有加入集合，就将他加入。
起初每个点的都是一个独立的集合，把边权从小到达排序，按照边权枚举边，用并查集判断两个是否在同一个集合，如果在一个集合就跳过当前边，反之就联通这两个集合。
O(mlogm)
二、Prim算法
每次选择当前点所连的边的最小值，然后把它连起来
有些类似Dijkstra
堆优化的算法时间复杂度为O(nlogn)
------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
微信打赏