算法设计与分析-5图论桥报告.docx

上传者: 51695846 | 上传时间: 2022-06-19 09:09:47 | 文件大小: 101KB | 文件类型: DOCX
仅供参考,copy冲查重塔峰 算法设计与分析-5图论桥报告.docx (1) 图的连通性。 (2) 并查集的基本原理和应用。 由上面的数据可以看出: 1. 在基准算法里深度优先DFS比并查集DSU效率高。 2. 在小规模数据由于深度不大,所以路径压缩效果不明显。 3. 将基准算法改为判断可达后时间可以缩短40%,效果较明显。 4. 通过查并集dsu+最近公共祖先lca的方法,可以避免大量的冗余计算,效果明显。 通过本次实验,我加深对图的连通性的理解和运用,直到如何利用深度优先DFS算法、广度优先BFS算法、查并集DSU算法生成生成树并确定连通性。掌握并查集的基本原理和应用,通过父亲数组father、查找find()、合并join()实现并查集,以确定图的连通性。同时也了解到通过路径压缩和按秩合并的并查集优化方法。路径压缩在图规模较大、树深度较大时效果会比较好。

文件下载

评论信息

免责申明

【只为小站】的资源来自网友分享,仅供学习研究,请务必在下载后24小时内给予删除,不得用于其他任何用途,否则后果自负。基于互联网的特殊性,【只为小站】 无法对用户传输的作品、信息、内容的权属或合法性、合规性、真实性、科学性、完整权、有效性等进行实质审查;无论 【只为小站】 经营者是否已进行审查,用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。
本站所有资源不代表本站的观点或立场,基于网友分享,根据中国法律《信息网络传播权保护条例》第二十二条之规定,若资源存在侵权或相关问题请联系本站客服人员,zhiweidada#qq.com,请把#换成@,本站将给予最大的支持与配合,做到及时反馈和处理。关于更多版权及免责申明参见 版权及免责申明