前言
春节放假会了老家，停更了很多天，这是年后连夜肝进去的第一篇文章，先来聊聊春节放假期间产生的事，这次回家遇到了我学生时代的女神，当年她在我心目中那是
"出淤泥而不染、濯清涟而不妖"
没想到这次回家遇到了她，身材发福了，心目中女神的形象霎时碎了，就如同达芬奇再次遇到了蒙娜丽莎
"菡萏香销翠叶残"
好了，言归正传。
有时候咱们能够须要判断在大型网络中两台计算机是否相连，是否须要建设一条新的连贯能力通信；或者是在社交网络中判断两个人是否是敌人关系（相连示意是敌人关系）。在这种利用中，通常咱们可能须要解决数百万的对象和数亿的连贯，如何可能疾速的判断出是否相连呢？这就须要应用到union-find算法
概念
相连
如果输出一对整数，其中每个数字示意的是某种对象（人、地址或者计算机等等），整数对p,q了解为“p与q相连”，相连具备以下个性：
- 自反性：p与p是相连的
- 对称性：如果p与q相连，那么q与p相连
- 传递性：如果p与q相连，q与r相连，那么p与r也相连
对象如何与数字关联起来，前面咱们聊到一种算法符号表
等价类
假如相连是一个种等价关系，那么等价关系可能将对象划分为多个等价类，在该算法中，当且仅当两个对象相连时他们才属于同一个等价类
触点
整个网络中的某种对象称为触点
连通重量
将整数对称为连贯，将等价类称作连通重量或者简称重量
动静连通性
union-find算法的指标是当程序从输出中读取了整数对p q时，如果已知的所有整数对都不能阐明p q是相连的，那么将这一对整数输入，否则疏忽掉这对整数；咱们须要设计数据结构来保留已知的所有整数对的信息，判断出输出的整数对是否是相连的，这种问题叫做动静连通性问题。
union-find算法API定义
public interface UF { void union(int p, int q); //在p与q之间增加一条连贯 int find(int p); //返回p所在重量的标识符 boolean connected(int p, int q); //判断出p与q是否存在于同一个重量中 int count(); //统计出连通重量的数量}如果两个触点在不同的重量中，union操作会使两个重量归并。一开始咱们有N个重量（每个触点示意一个重量），将两个重量归并之后数量减一。
形象实现如下：
public abstract class AbstractUF implements UF { protected int[] id; protected int count; public AbstractUF(int N) { count = N; id = new int[N]; for (int i = 0; i < N; i++) { id[i] = i; } } @Override public boolean connected(int p, int q) { return find(p) == find(q); } @Override public int count() { return count; }}接下来咱们就次要来探讨如何实现union办法和find办法
quick-find算法
这种算法的实现思路是在同一个连通重量中所有触点在id[]中的值都是雷同的，判断是否连通的connected的办法就是判断id[p]是否等于id[q]。
public class QuickFindImpl extends AbstractUF { public QuickFindImpl(int N) { super(N); } @Override public int find(int p) { return id[p]; } @Override public void union(int p, int q) { int pId = find(p); int qId = find(q); if (pId == qId) { //如果相等示意p与q曾经属于同一重量中 return; } for (int i = 0; i < id.length; i++) { if (id[i] == pId) { id[i] = qId; //把重量中所有的值都对立成qId } } count--; //连通重量数减一 }}- 算法剖析：
find()操作显然是很快的，工夫复杂度O(1), 然而union的算法是无奈解决大型数据的，因为每次都须要变量整个数组，那么union办法的工夫复杂度是O(n)
quick-union算法
为了进步union办法的速度，咱们须要思考另外一种算法；应用同样的数据结构，只是从新定义id[]示意的意义，每个触点所对应的id[]值都是在同一重量中的另一个触点的名称
在数组初始化之后，每个节点的链接都指向本人；id[]数组用父链接的模式示意了森林，每一次union操作都会找出每个重量的根节点进行归并。
public class QuickUnionImpl extends AbstractUF { public QuickUnionImpl(int N) { super(N); } @Override public int find(int p) { //找出p所在重量的根触点 while (p != id[p]) { p = id[p]; } return p; } @Override public void union(int p, int q) { int pRoot = find(p); //找出q p的根触点 int qRoot = find(q); if (pRoot == qRoot) { //处于同一重量不做解决 return; } id[pRoot] = qRoot; //根节点 count--; }}- 算法剖析：
看起来quick-union算法比quick-find算法更快，因为union不须要为每对输出遍历整个数组，
思考最佳状况下，find办法只须要拜访一次数组就能够失去根触点，那么union办法的工夫复杂度O(n)；
思考到最蹩脚的输出状况，如下图：
find办法须要拜访数组n-1次，那么union办法的工夫复杂度是O(n²)
加权quick-union算法
为了保障quick-union算法最蹩脚的状况不在呈现，我须要记录每一个树的大小，在进行重量归并操作时总是把小的树连贯到大的树上，这种算法结构进去树的高度会远远小于未加权版本所结构的树高度。
public class WeightedQuickUnionImpl extends AbstractUF { private int[] sz; public WeightedQuickUnionImpl(int N) { super(N); sz = new int[N]; for (int i = 0; i < N; i++) { sz[i] = 1; } } @Override public void union(int p, int q) { int pRoot = find(p); //找出q p的根触点 int qRoot = find(q); if (pRoot == qRoot) { //处于同一重量不做解决 return; } //小树合并到大树 if (sz[pRoot] < sz[qRoot]) { sz[qRoot] += sz[pRoot]; id[pRoot] = qRoot; } else { sz[pRoot] += sz[qRoot]; id[qRoot] = pRoot; } count--; } @Override public int find(int p) { //找出p所在重量的根触点 while (p != id[p]) { p = id[p]; } return p; }}- 算法剖析：
最坏的状况下，每次union归并的树都是大小相等的，他们都蕴含了2的n次方个节点，高度都是n，合并之后的高度变成了n+1，由此能够得出union办法的工夫复杂度是O(lgN)
总结
union-find算法只能判断出给定的两个整数是否是相连的，无奈给出具体达到的门路；前期咱们聊到图算法能够给出具体的门路
| 算法 | union() | find() |
|---|---|---|
| quick-find算法 | N | 1 |
| quick-union算法 | 树的高度 | 树的高度 |
| 加权quick-union算法 | lgN | lgN |
最初（点关注，不迷路）
文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。
最初，写作不易，请不要白嫖我哟，心愿敌人们能够点赞评论关注三连，因为这些就是我分享的全副能源起源????
文中所有源码已放入到了github仓库https://github.com/silently9527/JavaCore参考书籍：算法第四版
程序员罕用的IDEA插件：https://github.com/silently9527/ToolsetIdeaPlugin齐全开源的淘客我的项目：https://github.com/silently9527/mall-coupons-server
微信公众号：贝塔学Java