最小生成树笔记

无聊了再坑一坑图论吧。。。啥都搞不好。。。

给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树。。。

有两种著名的算法。。。prim，kruskal。。。

prim的效率取决于优先队列的实现与图的存储方式，这里记顶点数v，边数e 邻接矩阵:O(v²)、邻接表:O(elog₂v)，若用斐波那契堆作为优先队列则效率为O(e+vlog₂v)

kruskal的效率取决于并查集的实现，若用按秩合并与路径压缩效率为O(elog₂e)