试题程序及解题报告学校题目省选赛.pptxVIP

《算法艺术与信息学竞赛》

第二版

教学幻灯片

图论(刘汝佳)

内容介绍一、最小生成树二、唯一性判定三、K小生成树四、最小度限制生成树五、最小比率生成树六、逆向最小生成树

一、最小生成树连接每个点的连通图（一定是树）权和尽量小算法：一般算法BoruvkaPrimKruskal

一般最小生成树算法前提:无相等边维护生成森林Fe为无用边,若e的两个端点在F的同一个分量中,但e不在F中对于F的每一个分量从它出去(即恰好有一个端点在此分量内)的最小边为安全边不同的分量可以有相同的安全边结论:MST含有所有安全边,不含无用边.

一般最小生成树算法结论:MST含有所有安全边,不含无用边.证明假设有一个分量(黄色),它的安全边e不在T内.则u到v有唯一路径,它经过e’,它恰好有一个端点在黄色分量中.由于e是安全边,w(e)w’(e),用e替换e’得到更小的T’,矛盾加入无用边将形成环

Boruvka算法由Boruvka于1926年提出(早于图论产生!)

Boruvka算法每个分量设置’leader’,用DFS在m时间内求出检查每条边一次以修正各分量的安全边权第i次迭代每个分量大小至少为2i最多logV次迭代,总O(ElogV)

Prim算法只关心一棵树T,每次加入T的安全边用堆保存到每个顶点(而非边)的安全边Insert/ExtractMin调用V次,DecreaseKey调用E次二叉堆:O((E+V)logV),Fibonacci堆:O(E+VlogV)

Prim算法算法框架

Kruskal算法把边从小到大排序,一般情况为O(ElogE)每次填加一个安全边如何知道边是否安全?并查集,每次约O(1)

二、MST唯一性判定考虑一般最小生成树算法每一个分量出发安全边唯一,不特殊处理,否则若同时添加会形成环,一定不唯一若同时添加不会形成环,类似正确性证明,即:假设某边e不在T中,对应的e’一定比e大而不可能相等

二、MST唯一性判定时间复杂度Boruvka:不变(只在和安全边比较时修改)Prim:不变(只在判断顶点标号时修改)Kruskal:不变(相等的边时特殊处理)另一种思路:最小=第二小

三、K小生成树交换：(+e,-e’)思路：前k小生成树集合的“邻树集”中最小的一个可作为第k小生成树