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