笔试算法题(38):并查集(Union-Find Sets)
2024-09-04 18:21:53
议题:并查集(Union-Find Sets)
分析:
一种树型数据结构,用于处理不相交集合(Disjoint Sets)的合并以及查询;一开始让所有元素独立成树,也就是只有根节点的树;然后根据需要将关联的元素(树)进行合并;合并的方式仅仅是将一棵树最原始的节点的父亲索引指向另一棵树;
优化:加入一个rank数组存储节点深度的下界(从当前节点到其最远子节点的距离),从而可以启发式的对树进行合并,从而减少树的深度,防止树的退化;使 得包含较少节点的树根指向包含较多节点的树根,具体指代为树的高度;另一个优化就是路径压缩,尽可能将子节点都直接连接到根节点之后;
并查集的空间复杂度为O(N),构建一个集合的时间复杂度为O(N);压缩后的查找复杂度是一个很小的常数;应用:Kruskal算法求最小生成树中判断新加入的边是否在同一棵树内部;两个节点的最近公共祖先(Least Common Ancestors);
初始化father:各个节点独立成树,并且其father[i]=i,也就是其父节点就是其自身;
father[i]
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9初始化rank:各个节点为根节点,所以高度都为1;
rank[i]
0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 1 1 1 1合并2和6:由于rank[2]=rank[6],所以将2的父亲索引指向6,这样2和6就在同一棵树;并需将6的rank值增加1;
father[i]
0 1 2 3 4 5 6 7 8 9
0 1 6 3 4 5 6 7 8 9
rank[i]
0 1 2 3 4 5 6 7 8 9
1 1 1 1 1 1 2 1 1 1
样例:
int *father;
int *rank; /**
* 并查集的初始化:
* 数组father中的元素在最开始ide时候都是独立的树,也就是只有根节点
* 的树,数组father的下标i表示节点,而father[i]的值表示i节点的父亲
* 节点;rank[i]=1表示一开始所有树节点的高度都为1
* */
void init(int cap) {
father=new int[cap];
rank=new int[cap];
/**
* 时间复杂度为O(N)
* */
for(int i=;i<;i++) {
father[i]=i;
rank[i]=;
}
} void clean() {
delete [] father;
delete [] rank;
}
/**
* 查找元素所在的集合并进行路劲压缩:
* 由于需要频繁使用GetFather()函数,并且其时间复杂度受树结构影响;
* 当元素较多的时候,集合退化成链表,则GetFather()需要O(N),所以
* 需要对其进行优化,每次调用GetFather()的时候都将输入元素压缩成
* 最原始父亲节点的直接子节点
* */
int GetFather(int son) {
if(father[son]==son)
return son;
else {
father[son]=GetFather(father[son]);
return father[son];
}
} /**
* 合并两个不相交的集合:
* 输入元素x和y来自两个不相交的集合,找到其最原始的父亲节点
* 并将一个原始父亲节点设置为另一个原始父亲节点的父亲节点
* */
void Union1(int x, int y) {
/**
* GetFather()为递归寻找输入节点的最原始的父亲节点
* */
int fx=GetFather(x);
int fy=GetFather(y);
/**
* 判断x和y是否来自同一棵树,如果不是才进行赋值;其实可以
* 不同进行判断(省去if语句)
* 注意最原始父亲节点的father[i]=i;
* */
if(fx!=fy)
father[fx]=fy;
} /**
* 利用rank加权数组启发式进行合并
* */
void Union2(int x, int y) {
int fx=GetFather(x);
int fy=GetFather(y); if(fx==fy) return;
/**
* rank[fx]较大,说明其越靠近根节点,则将
* fy连接到其后面可以压缩路径
* */
if(rank[fx]>rank[fy])
father[fy]=fx;
else {
if(rank[fx]==rank[fy])
rank[fy]++;
father[fx]=fy;
}
} /**
* 判断两个元素是否属于同一个集合:
* 利用GetFather()函数判断其最原始父亲节点是否相同
* */
bool IsSameSet(int x, int y) {
return GetFather(x)==GetFather(y);
}
最新文章
- IBatis和Hibernate区别
- java中创建字符串的两种方式(“”与new String())及区别
- 柱状堆积图Echarts
- 不错的 iOS 开发辅助工具
- js获取项目根路径
- C#中反射的使用(How to use reflect in CSharp)(3)Emit的使用
- Oracle学习第一天---安装和基础入门
- [CF940F]Machine Learning
- 初识 .net core和vs code
- Web前端教程3-JavaScript教程
- 如何在webpack中成功引用到图片?
- 搭建MHA测试
- [20190227]简单探究tab$的bojb#字段.txt
- python 面向对象(一)初识面向对象
- repos配置
- 使用Jupyter lab前应该读的几篇文章
- vue---设置缩进为4个空格
- 在 Confluence 6 中连接一个 LDAP 目录
- Redesign Your App for iOS 7 之 页面布局
- POSIX 进程间通信 (可移植操作系统接口)
热门文章
- Linux网络流量实时监控ifstat iftop命令详解(转载)
- Android系统中setprop,getprop,watchprops命令的使用(转载)
- maven仓库错误
- ThinkPHP3.2.3学习笔记1---控制器
- bzoj 4823: [Cqoi2017]老C的方块【最大权闭合子图】
- VS2010创建C++静态链接库创建和使用
- shell 调试 2例
- jsp声明周期
- 解决 图片在div中等比例缩放问题 (未解决:图片比例小于盒子模型时不会自动填充)
- php判断是否引入某文件