find算法

⑴ 如何检测社交网络中两个人是否是朋友关系（union-find算法）

春节放假会了老家，停更了很多天，这是年后连夜肝出来的第一篇文章，先来聊聊春节放假期间发生的事，这次回家遇到了我学生时代的女神，当年她在我心目中那是

没想到这次遇到了她，身体发福，心目中女神的形象瞬间碎了，就像达芬奇再次遇到了蒙娜丽莎

好了，言归正传。

有时候我们可以需要判断在大型网络中两台计算机是否相连，是否需要建立一条新的连接才能通信；或者是在社交网络中判断两个人是否是朋友关系（相连表示是朋友关系）。在这种应用中，通常我们可能需要处理数百万的对象和数亿的连接，如何能够快速的判断出是否相连呢？这就需要使用到union-find算法

假如输入一对整数，其中每个数字表示的是某种对象（人、地址或者计算机等等），整数对p,q理解为“p与q相连”，相连具有以下特性：

假设相连是一个种等价关系，那么等价关系能够将对象划分为多个等价类，在该算法中，当且仅当两个对象相连时他们才属于同一个等价类

整个网络中的某种对象称为触点

将整数对称为连接，将等价类称作连通分量或者简称分量

union-find算法的目标是当程序从输入中读取了整数对p q时，如果已知的所有整数对都不能说明p q是相连的，那么将这一对整数输出，否则忽略掉这对整数；我们需要设计数据结构来保存已知的所有整数对的信息，判断出输入的整数对是否是相连的，这种问题叫做动态连通性问题。

如果两个触点在不同的分量中，union操作会使两个分量归并。一开始我们有N个分量（每个触点表示一个分量），将两个分量归并之后数量减一。

抽象实现如下：

接下来我们就主要来讨论如何实现union方法和find方法

这种算法的实现思路是在同一个连通分量中所有触点在id[]中的值都是相同的，判断是否连通的connected的方法就是判断id[p]是否等于id[q]。

为了提高union方法的速度，我们需要考虑另外一种算法；使用同样的数据结构，只是重新定义id[]表示的意义，每个触点所对应的id[]值都是在同一分量中的另一个触点的名称

在数组初始化之后，每个节点的链接都指向自己；id[]数组用 父链接 的形式表示了 森林 ，每一次union操作都会找出每个分量的 根节点 进行模猛归并。

find方法需要访问数组n-1次，那么union方法的时间复杂度是O(n²)

为了保证quick-union算法最糟糕的情况不在出现，我需要记录每一个树的大小，在进行分量归并操作时总是把小的树连接到稿消大的树上，这种算法构造出来树的高度会远远小于未加权版本所构造的树高度。

union-find算法只能判断出给定的两个整旦敬桥数是否是相连的，无法给出具体达到的路径；后期我们聊到图算法可以给出具体的路径

文中或许会存在或多或少的不足、错误之处，有建议或者意见也非常欢迎大家在评论交流。

最后， 写作不易，请不要白嫖我哟 ，希望朋友们可以 点赞评论关注 三连，因为这些就是我分享的全部动力来源🙏

⑵ 使用加权规则和压缩规则实现UNION和FIND算法

UNION(1,2);UNION(3,4);UNION(5,6);UNION(7,8);UNION(1,3);UNION(5,7);
FIND(8); 输出结果慎梁亏是5；
UNION(1,5);
FIND(8); 输出结果是1.
我所理解的Find（i）算法是将含有i的parent暂时（在合宽神并的过程中的父母）记住，然后继续合并一些集合之后在进行查找，就可以在刚渣拦刚所求得的parent的基础上继续查找，提高了效率。