南京优化网站,免费自适应网站模板,怎么修改php网站,如何制作个人网页兼职文章目录 逻辑结构存储结构并、查代码实现Union 操作的优化Find 操作的优化#xff08;压缩路径#xff09; 逻辑结构
集合#xff1a;将各个元素划分为若干个互不相交的子集的集合 森林是m(m0)棵互不相交的树的集合
存储结构
#define SIZE 13
int UFSets[SIZE]; … 文章目录 逻辑结构存储结构并、查代码实现Union 操作的优化Find 操作的优化压缩路径 逻辑结构
集合将各个元素划分为若干个互不相交的子集的集合 森林是m(m0)棵互不相交的树的集合
存储结构
#define SIZE 13
int UFSets[SIZE]; // 集合元素数组// 初始化并查集
void Initial(int S[]){for(int i0;iSIZE;i)S[i] -1;
}并、查代码实现
// Find 查操作找x所属集合返回x所属的根结点 时间复杂度On
int Find(int S[],int x){while(S[x]0) // 循环寻找x的根xS[x];return x; // 根的S【】小于0
}// Union 并操作将两个集合合并为一个 时间复杂度On
void Union(int S[],int Root1,int Root2){// 要求Root1与Root2是不同的集合if(Root1Root2) return// 将根Root2连接到另一根Root1下面S[Root2]Root1;Union 操作的优化
优化思路在每次Union操作构建树的时候尽可能让树不长高 ①用根结点的绝对值表示树的结点的总数 ②Union操作让小树合并到大树
// Union 并操作小树合并到大树 时间复杂度Olog2(n)
void Union(int S[],int Root1,int Root2){if(Root1Root2) return;if(S[Root2]S[Root1]){ // Root2 结点数更少S[Root1] S[Root2]; // 累加结点总数S[Root2] Root1; // 小树合并大树} else{S[Root2] S[Root1];S[Root1] Root2;}
}Find 操作的优化压缩路径
优化思路先找到根结点再将查找路径上所有结点都挂到根结点上
int Find(int S[],int x){int root x;while(S[root]0) rootS[root]; // 循环找到根while(x!root){ // 压缩路径int tS[x]; // t指向x的父节点S[x] root; // x直接挂到根结点上xt;}return root; // 返回根结点编号
}
