算法设计与分析-5图论桥pre ppt.pptx

仅供参考，copy冲查重塔峰 算法设计与分析-5图论桥pre ppt.pptx （1） 图的连通性。 （2） 并查集的基本原理和应用。 找出一个无向图中所有的桥 数据获取 边稀疏 空间浪费 基准算法 深度优先dfs 查并集dsu 高效算法 dfs基准算法优化(判断可达) 查并集+最小公共祖先 数据处理 基准算法:DFS比DSU效率高。 小规模数据:深度不大，路径压缩效果不明显。 判断可达后时间缩短40%，效果较明显。 dsu+lca可避免大量冗余计算，效果明显。   图的连通性 DFS、BFS、DSU生成生成树:连通性。 DSU：父亲数组father、查找find()、合并join() 路径压缩和按秩合并