1 / 19
文档名称:

算法合集之《维护森林连通性-动态树》.ppt

格式:ppt   大小:3,262KB   页数:19页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

算法合集之《维护森林连通性-动态树》.ppt

上传人:165456465 2025/3/15 文件大小:3.19 MB

下载得到文件列表

算法合集之《维护森林连通性-动态树》.ppt

文档介绍

文档介绍:该【算法合集之《维护森林连通性-动态树》 】是由【165456465】上传分享,文档一共【19】页,该文档可以免费在线阅读,需要了解更多关于【算法合集之《维护森林连通性-动态树》 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。维护森林连通性——动态树
PLEASE ENTER YOUR TITLE HERE
华东师大二附中
陈首元
维护一个森林
01
支持边的插入与删除
02
支持树的合并与分离
03
支持寻找路径上费用最小的边
04
所有操作的均摊复杂度为O(logN)
05
动态树
2
3
4
5
6
7
8
1
10
20
-20
0
30
-5
-5
Root(1,2,3,4,5,6,7,8)=1
MinCost(6)=10
Update(7,10)
5
40
Evert(6)
新树根
Cut(4)
Root(7,8)=4
Link(3,4,10)
Evert(v)使v成为新的根,并将v到原树根上的边反向
Cut(v)删除v与其父节点连接的边
Link(v,w,x)将以v为根的树连接到节点root(w)上,(v,w)的费用为x
Update(v,x)使v到树根路径上的边的费用+x
MinCost(v) 返回v到根路径上费用最小的边
Root(v) 返回包含节点v的树的根
动态树的基本操作
将树中的边分为实边、虚边两种,每个节点最多向其子节点连出一条实边
将树划分为一些完全由实边组成的路径,只对这些路径进行操作
01
02
操作的实现


一条路径
路径的基本操作
Path(v):返回包含v的路径 (每个路径有一个标志)
Head(p),Tail(p):返回首节点、尾节点
Pmincost(p):返回p中费用最小的边
Pupdate(p,x:real):将p中每条边的费用+x
Reverse(p):将p中的每条边反向
Concatenate(p,q,x) :添加边(tail(p),head(q))费用为x,将路径p,q合并
Split(v):将v从路径中删除并把路径分为两部分
Splice
01
Splice(p) :将路径p向更靠近根的方向增长
实现方法:把虚边(tail(P),Parent(p)) 变为实边,为了维护实边的性质,将原来从Parent(P)中连出的边设为虚边
02
Expose
1
Expose(v):将从v到树根路径上的所有边设为实边
实现方法:不断调用splice直到根为止
2
有了Expose(v),就可以实现所有动态树操作了
3
Procedure Link(v,w:vertex;x:real);
01
02
03
04
Begin
Concatenate(path(v),expose(w),x);
End;
Link操作

最近更新

基于测录井资料的J油田储层分类研究 2页

幼儿园2019-2020年保育员五级职业水平考试试题.. 11页

2020-2025年中国游泳镜行业市场前景预测及投资.. 20页

基于模糊控制的自动供水教学系统的设计 2页

2025年交换过后才知道续写作文 6页

基于标签和关联规则挖掘的图书组合推荐系统模.. 2页

2020-2025年中国植物防脱洗发液市场前景预测及.. 23页

2025年五彩池教学设计优秀 20页

能源基础设施建设项目合同工程方案 7页

基于有补T-范的F-命题演算和一类F-控制模型 2页

2025年护士毕业实习总结 9页

2025年护士心得体会600字范文 17页

2025年护士年终简短工作总结 9页

2025年五年级苹果的作文 6页

2025年护士年终个人总结简短2025 13页

2025年护士工作述职报告范文 19页

2025年护士工作总结5篇 12页

2025年五年级数学教案异分母分数的加、减法 7页

基于改进同伦迭代法对病态潮流的研究 2页

基于控制流模型的Web系统测试方法研究 2页

人工智能与行业应用-全面剖析 43页

2025年护士学习的心得 4页

股权转让合同变更登记协议 5页

2019-2025年中国自动铅笔行业发展潜力分析及投.. 23页

校园网络工程设计-网络工程课程设计报告 32页

煤矿综采工作面三机选型 10页

物业续聘管理方案 4页

六年级下册平面图形的认识练习题 4页

第10课桥梁模型-设计与制作 2页

液相色谱-质谱联用仪期间核查操作规程 3页