并查集（数据结构）

逻辑结构集合的逻辑结构存储结构用互不相交的树表示多个“集合”顺序存储的树双亲表示法因为要索引根节点#defineMAX_TREE_SIZE100//树中最多结点数typedefstruct{//树的结点定义ElemType data;//数据元素intparent;//双亲位置域}PTNode;typedefstruct{//树的类型定义PTNode nodes[MAX_TREE_SIZE];//双亲表示intn;//结点数}PTree;基本操作#初始化#defineSIZE13intUFSets[SIZE];//集合元素数组//初始化并查集voidInitial(intS[]){for(inti0;iSIZE;i)S[i]-1;}#“查”到一个元素到底属于哪一个集合——从指定元素出发一路向北找到根节点//Find 查操作找x所属集合返回x所属根结点intFind(intS[],intx){//x是数组下标while(S[x]0)//循环寻找x的根xS[x];returnx;//根的S[]小于0}最坏时间复杂度O(n),n个元素一个链表树从底部开始查找#如何判断两个元素是否属于同一个集合——分别查到两个元素的根判断根节点是否相同即可#如何把两个集合“并”为一个集合——让一棵树成为另一棵树的子树即可//Union 并操作将两个集合合并为一个voidUnion(intS[],intRoot1,intRoot2){//要求Root1与Root2是不同的集合if(Root1Root2)return;//将根Root2连接到另一根Root1下面S[Root2]Root1;}时间复杂度O(1)#Union操作的优化尽量让小树合并到大树树的高度不增加降低查“的时间复杂度用根节点的绝对值表示树的结点总数//Union 并操作小树合并到大树voidUnion(intS[],intRoot1,intRoot2){if(Root1Root2)return;if(S[Root2]S[Root1]){//Root2结点数更少S[Root1]S[Root2];//累加结点总数S[Root2]Root1;//小树合并到大树}else{S[Root2]S[Root1];//累加结点总数S[Root1]Root2;//小树合并到大树}}该方法构造的树高不超过⌊ l o g 2 n ⌋ 1 \lfloor log_2n \rfloor 1⌊log2​n⌋1并查集的进一步优化#find操作的进一步优化压缩路径策略//Find 查操作优化先找到根节点 再进行压缩路径intFind(intS[],intx){introotx;while(S[root]0)rootS[root];//循环找到根while(x!root){//压缩路径inttS[x];//t指向x的父节点S[x]root;//x直接挂到根节点下xt;}returnroot;//返回根节点编号}