总结一下最小生成树,并且放一下模板。
假设 n 表示点数,m 表示边数。
Prim算法
适用条件:
适用于稠密图,时间复杂度 O(n^2)。
核心思想:
每次挑一条与当前集合相连的最短边。
代码
1 | //prim 算法 类似与dijkstra算法 总是维护最小生成树的一部分 |
堆优化的prim
1 | //prim 堆优化 |
Kruskal算法
适用条件:
适用于稀疏图,时间复杂度 O(mlogm)。
核心思想:
从小到大挑不多余的边。
代码:
1 | const int maxn=1e4+5; |
当时直接套并查集写的,显得有点冗余
题目的话,以后有时间再放。