生成树的定义:对于一个图G,获取G的边使得所有的顶点都连接到。最小生成树(MST Minimun spanning tree):给定图G(V,E),以及对应的边的权重,获取一颗总权重最小的生成树。
树的定义:连接的无环图
找到所有的生成树,然后计算权重最小的
假如边e={u,v}是某个MST的一条边,通过对合并这两个顶点为一个新的顶点(这种操作称作contract e),将有多条边同时连接多个顶点的合并成一个权重最小的边保留,其它边的连接形式保持不变。可以证明假设T'是G/e(不包含e的G)的MST,那么T'U{e}也是G的MST
红色的线即 crossing cut的边
假设T是G的一个MST,那么它必定存在一条边e'={u',v'}横跨S和V/S,由于w(e)<=w(e'),可以构造T'=T/{e'}U{e}=w(T)-w(e')+w(e)<=w(T),也就是说T'也是MST,e属于某个MST。
维护一个优先级队列Q,它的节点u.key=min{w(u,v)|u in s and v in (S-V)}
初始的图如下
选取节点s in S,其它的为V-S 按照初始化的规则得到
然后获取最小key的节点,显然他就是S
获取S的所有邻接表,比较crossing cut的边的权值和当前Q中存储的key的大小,保留小的,得到
再找到Q中最小的为A,将两者记下来
再查看所有S的邻接表,更新Q的权值,得到
获取最小值为5,将它放入S中
再次更新Q得到
获取最小是为6,得到
再更新Q
最小值为8
更新Q得到
最小值为3
更新Q得到
最小值为9
更新Q得到
最小值为15
最终得到MST为
在整个过程中,涉及V次的从优先级队列中获取最小值,以及边两倍次的减少key的值,所以总的时间为
使用斐波那契堆可以达到VlgV+E
核心思想:全局最小的corssing cut边必定属于最小生成树,这个过程不能生成环,需要追踪两个节点是否已经互相连接了
追踪的数据结构是 Union-Find 结构,包含3个功能,Make-Set:创建一个集合;Find-Set:找到当前元素在那个集合;Union:合并集合
在使用Union-Find数据结构的基础上能够做到时间为O(ElgE+Eα(V)),假设权重为正整数而且最大值是个常量,那么排序可以达到常量的时间,这个时候,算法所需要的时间就是O(E),整体不Prims算法要好
最快的MST 算法运行期望时间是O(V+E),Karger, Klein, and Tarjan 1993发明