并查集三要素思维脑图思维导图
并查集数据结构三要素内容详解
树图思维导图提供 并查集三要素思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 并查集三要素思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：12efe23520c80b426b7d839defa192a1
思维导图大纲
并查集思维导图模板大纲
三要素
逻辑结构
元素之间为集合关系
基本操作
初始化
初始化并查集，并将所有数组元素初始化为1
Find(S[],x)
查：找到元素x所属集合
Union(S[],root1,root2)
并：将集合ROOT2合并到集合ROOT1下，成为一个集合
存储结构
顺序存储，每个集合组织成一棵树，采用“双亲表示法”
代码
掌握
Union优化
根节点的绝对值表示一棵树（集合）的结点总数
Union操作合并两棵树时，把小树合并到大树下
Find优化
压缩路径，先找到根节点，再把查找路径上所有结点挂到根节点下
压缩路径代码，第一次循环找到根设为root，第二次循环时要保存父节点t，再把x挂到根下
优化之后时间复杂度
优化，知道α(n)远远小于logn就行
并查集用处
实现克鲁斯卡尔（Kruskal）算法
判断无向图连通性
每遍历到一条边，将边连接的两个顶点合并到同一个集合中
处理完所有边后只要是连通的顶点都会合并到同一个子集中，不连通的顶点一定在不同的子集中
用于判断和构造等价类
相关思维导图模板
树图思维导图提供 专注力训练思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 专注力训练思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：ca6435a61cc80f311c29ac82082d8e36
树图思维导图提供 香山精神研究思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 香山精神研究思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：3d8d880662a5489d30d081f5083ee3dd
沪公网安备 31011502019485号
上海工商