首页 > 最小生成树

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

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

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

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

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

继续阅读→

阅读全文