并查集是如何优化好友关系查询的暴力算法的编者在一次讨论中忽然发现自己竟然忘记了并查集这一个概念曾记得听说别人介绍过但是彻底的忘了所幸再次学习了一遍下面是引入。在第一次写判断两个人是不是朋友这类问题时相信很多读者都会想到用最直接的办法从一个人开始沿着朋友链一步步找看能不能走到另一个人那里。比如问张三和李四是不是朋友如果张三的朋友名单里有王五王五的朋友名单里有赵六赵六的朋友名单里又有李四那他们确实是朋友关系。但如果关系网很大每次查询都要这样绕来绕去地找数据量一上来就很容易超时。今天我们带来的这个数据结构能够让你在这种关系查询上获得接近瞬间完成的效率。一个简单的类比假设有五个人张三、李四、王五、赵六、孙七编号从零到四。一开始大家互不相识每个人都是自己门派的掌门人。现在发生了几件事张三和李四结拜成了兄弟王五和赵六因为同门之谊走得很近后来李四又在一次偶遇中和王五一见如故也结为好友。这时候有人问张三和赵六认识吗如果你沿着关系链找会发现张三认识李四李四认识王五王五又认识赵六所以答案是肯定的。但如果江湖上有几万人关系错综复杂每次有人问某两个人认不认识你都要从头到尾捋一遍关系链恐怕算到天亮也算不完。这时候我们就需要一种方法能够把这些间接的朋友关系直接体现出来让查询变得简单直接。并查集的核心思想并查集解决这个问题的思路很朴素既然张三和李四是朋友李四和王五也是朋友王五和赵六也是朋友那这四个人其实就在同一个朋友圈里。我们可以选其中一个人作为这个圈子的代表或者说掌门人。以后判断两个人是不是朋友就只需要看他们的掌门人是不是同一个人就行了。具体实现上我们用一个数组来记录每个人的上级是谁。一开始的时候每个人都是自己的上级。当两个人成为朋友时我们就把其中一个人的掌门人的上级设成另一个人的掌门人这样两个门派就合并成了一个大门派。查找与合并的过程查找操作就是要找到某个人所在的门派的终极掌门人。如果一个人的上级就是他自己那他就是掌门如果不是就继续往上找直到找到那个上级为自己的人。这里有个问题如果关系链很长比如张三的上级是李四李四的上级是王五王五的上级是赵六这样一层层找上去在最坏的情况下时间复杂度会退化成线性和暴力遍历没什么区别。于是就有了路径压缩这个技巧。它的思想很简单既然我们都要找到张三的掌门人是赵六那为什么不让张三直接记住赵六呢下次再查的时候就不用走那么多弯路了。具体做法是在查找的过程中把沿途遇到的每个人的上级都直接设置为最终找到的根节点。这样一来原本可能很长的关系链就会被压平变成几乎所有人直接指向掌门人的结构。合并操作则是在两个门派联姻时使用。我们先分别找到两个人的掌门人如果已经是同一个人那说明他们本来就属于同一个群体如果不是就让其中一个掌门人的上级变成另一个掌门人。为了尽量保持树的平衡避免一边倒的情况我们可以记录每个树的高度让矮的树并入高的树。看看数组是如何变化的让我们用具体的数字来看看这个过程。初始状态下五个人的上级数组就是这样的零一二三四每个人自成一派。当张三和李四成为朋友后我们找到张三的根是零李四的根是一让零的上级变成一数组就变成了一、一、二、三、四。这时候张三是李四的小弟李四还是自己的掌门人。接着王五和赵六成为朋友找到二的根是二三的根是三让二的上级变成三数组变成一、一、三、三、四。现在王五成了赵六的小弟。关键的一步来了李四和王五成为朋友。我们找到李四的根是一再找王五的根二的上级是三三的上级是三所以王五的掌门人是三。现在我们要把李四和三合并让一的上级变成三数组就变成了 一、三、三、三、四。现在来看看查询的效果。有人问张三和赵六是不是朋友找张三的根零的上级是一一的上级是三三的上级是三所以根是三找赵六的根直接就是三。两人根相同确实是朋友。而且经过这次查找张三的上级路径被压缩了零会直接指向三下次再查就更快了。C语言代码实现下面是用C语言实现的完整代码#includestdio.h#includestdlib.htypedefstruct{int*parent;// 记录每个人的上级int*rank;// 记录树的高度intsize;}UnionFind;UnionFind*createUnionFind(intn){UnionFind*uf(UnionFind*)malloc(sizeof(UnionFind));uf-parent(int*)malloc(n*sizeof(int));uf-rank(int*)malloc(n*sizeof(int));uf-sizen;for(inti0;in;i){uf-parent[i]i;// 初始时每个人都是自己的上级uf-rank[i]0;}returnuf;}// 查找带路径压缩intfind(UnionFind*uf,intx){if(uf-parent[x]!x){uf-parent[x]find(uf,uf-parent[x]);// 递归查找并压缩路径}returnuf-parent[x];}// 合并voidunionSet(UnionFind*uf,intx,inty){intpxfind(uf,x);intpyfind(uf,y);if(pxpy)return;// 已经在同一个集合// 让矮树并入高树保持平衡if(uf-rank[px]uf-rank[py]){inttemppx;pxpy;pytemp;}uf-parent[py]px;if(uf-rank[px]uf-rank[py]){uf-rank[px];}}// 判断是否连通intisConnected(UnionFind*uf,intx,inty){returnfind(uf,x)find(uf,y);}intmain(){intn5;UnionFind*ufcreateUnionFind(n);// 建立关系0-1, 2-3, 1-2unionSet(uf,0,1);unionSet(uf,2,3);unionSet(uf,1,2);printf(张三(0)和赵六(3)是否认识%s\n,isConnected(uf,0,3)?是:否);printf(张三(0)和孙七(4)是否认识%s\n,isConnected(uf,0,4)?是:否);free(uf-parent);free(uf-rank);free(uf);return0;}这段代码最关键的就是 find 函数中的那一行递归赋值操作它让查找路径上的每个节点都直接指向根节点从而保证后续查询几乎可以在常数时间内完成。与暴力算法的对比如果没有并查集我们通常会怎么解决这个问题呢大多数人可能会想到用链表或者数组存储每个人的直接朋友每次查询就从一个朋友列表跳到另一个朋友列表直到找到目标或者遍历完所有可能。想象一下这样的场景在一个有十万个用户的社交网络中有五十万条好友关系现在要进行十万次查询。如果用遍历的方法每次查询都可能要跳转很多次累计下来的计算量会让程序运行得很慢。而使用并查集除了最开始需要线性时间初始化之外后续的每次合并和查询操作都只需要极短的时间几乎是瞬间完成。当然并查集也有它的局限性它适合处理关系只增不减的情况。如果今天两人还是朋友明天又绝交了并查集就不好直接处理这种删除操作。实际应用场景并查集在实际开发中有很多巧妙的应用。比如在社交网络中判断两个用户是否属于同一个圈子或者合并两个群组都可以用它来实现。在图像处理中如果我们想识别一张照片中哪些像素点属于同一个物体可以用并查集来合并相邻的相似像素。一开始每个像素都是独立的如果相邻两个像素颜色相近就把它们合并到同一个集合中最后统计有多少个集合就知道有多少个物体。在网络连接问题中判断两台计算机是否可以通过网络互相通信也可以用并查集来维护连通状态。当建立新的网络连接时就是合并操作查询两台机器是否连通就是查找操作。总结并查集算法的精髓在于用树结构来维护集合关系通过路径压缩这个技巧几乎可以将单次查询的时间复杂度降到常数级别。它的代码实现简洁思路直观特别适合处理那些动态添加关系的连通性问题。理解并查集的关键在于明白那个 parent 数组背后的树形结构以及递归查找过程中路径压缩是如何将长链变短、让查询变快的。掌握了这个数据结构你就拥有了解决大规模关系查询问题的利器。
并查集是如何优化好友关系查询的暴力算法的？
并查集是如何优化好友关系查询的暴力算法的编者在一次讨论中忽然发现自己竟然忘记了并查集这一个概念曾记得听说别人介绍过但是彻底的忘了所幸再次学习了一遍下面是引入。在第一次写判断两个人是不是朋友这类问题时相信很多读者都会想到用最直接的办法从一个人开始沿着朋友链一步步找看能不能走到另一个人那里。比如问张三和李四是不是朋友如果张三的朋友名单里有王五王五的朋友名单里有赵六赵六的朋友名单里又有李四那他们确实是朋友关系。但如果关系网很大每次查询都要这样绕来绕去地找数据量一上来就很容易超时。今天我们带来的这个数据结构能够让你在这种关系查询上获得接近瞬间完成的效率。一个简单的类比假设有五个人张三、李四、王五、赵六、孙七编号从零到四。一开始大家互不相识每个人都是自己门派的掌门人。现在发生了几件事张三和李四结拜成了兄弟王五和赵六因为同门之谊走得很近后来李四又在一次偶遇中和王五一见如故也结为好友。这时候有人问张三和赵六认识吗如果你沿着关系链找会发现张三认识李四李四认识王五王五又认识赵六所以答案是肯定的。但如果江湖上有几万人关系错综复杂每次有人问某两个人认不认识你都要从头到尾捋一遍关系链恐怕算到天亮也算不完。这时候我们就需要一种方法能够把这些间接的朋友关系直接体现出来让查询变得简单直接。并查集的核心思想并查集解决这个问题的思路很朴素既然张三和李四是朋友李四和王五也是朋友王五和赵六也是朋友那这四个人其实就在同一个朋友圈里。我们可以选其中一个人作为这个圈子的代表或者说掌门人。以后判断两个人是不是朋友就只需要看他们的掌门人是不是同一个人就行了。具体实现上我们用一个数组来记录每个人的上级是谁。一开始的时候每个人都是自己的上级。当两个人成为朋友时我们就把其中一个人的掌门人的上级设成另一个人的掌门人这样两个门派就合并成了一个大门派。查找与合并的过程查找操作就是要找到某个人所在的门派的终极掌门人。如果一个人的上级就是他自己那他就是掌门如果不是就继续往上找直到找到那个上级为自己的人。这里有个问题如果关系链很长比如张三的上级是李四李四的上级是王五王五的上级是赵六这样一层层找上去在最坏的情况下时间复杂度会退化成线性和暴力遍历没什么区别。于是就有了路径压缩这个技巧。它的思想很简单既然我们都要找到张三的掌门人是赵六那为什么不让张三直接记住赵六呢下次再查的时候就不用走那么多弯路了。具体做法是在查找的过程中把沿途遇到的每个人的上级都直接设置为最终找到的根节点。这样一来原本可能很长的关系链就会被压平变成几乎所有人直接指向掌门人的结构。合并操作则是在两个门派联姻时使用。我们先分别找到两个人的掌门人如果已经是同一个人那说明他们本来就属于同一个群体如果不是就让其中一个掌门人的上级变成另一个掌门人。为了尽量保持树的平衡避免一边倒的情况我们可以记录每个树的高度让矮的树并入高的树。看看数组是如何变化的让我们用具体的数字来看看这个过程。初始状态下五个人的上级数组就是这样的零一二三四每个人自成一派。当张三和李四成为朋友后我们找到张三的根是零李四的根是一让零的上级变成一数组就变成了一、一、二、三、四。这时候张三是李四的小弟李四还是自己的掌门人。接着王五和赵六成为朋友找到二的根是二三的根是三让二的上级变成三数组变成一、一、三、三、四。现在王五成了赵六的小弟。关键的一步来了李四和王五成为朋友。我们找到李四的根是一再找王五的根二的上级是三三的上级是三所以王五的掌门人是三。现在我们要把李四和三合并让一的上级变成三数组就变成了 一、三、三、三、四。现在来看看查询的效果。有人问张三和赵六是不是朋友找张三的根零的上级是一一的上级是三三的上级是三所以根是三找赵六的根直接就是三。两人根相同确实是朋友。而且经过这次查找张三的上级路径被压缩了零会直接指向三下次再查就更快了。C语言代码实现下面是用C语言实现的完整代码#includestdio.h#includestdlib.htypedefstruct{int*parent;// 记录每个人的上级int*rank;// 记录树的高度intsize;}UnionFind;UnionFind*createUnionFind(intn){UnionFind*uf(UnionFind*)malloc(sizeof(UnionFind));uf-parent(int*)malloc(n*sizeof(int));uf-rank(int*)malloc(n*sizeof(int));uf-sizen;for(inti0;in;i){uf-parent[i]i;// 初始时每个人都是自己的上级uf-rank[i]0;}returnuf;}// 查找带路径压缩intfind(UnionFind*uf,intx){if(uf-parent[x]!x){uf-parent[x]find(uf,uf-parent[x]);// 递归查找并压缩路径}returnuf-parent[x];}// 合并voidunionSet(UnionFind*uf,intx,inty){intpxfind(uf,x);intpyfind(uf,y);if(pxpy)return;// 已经在同一个集合// 让矮树并入高树保持平衡if(uf-rank[px]uf-rank[py]){inttemppx;pxpy;pytemp;}uf-parent[py]px;if(uf-rank[px]uf-rank[py]){uf-rank[px];}}// 判断是否连通intisConnected(UnionFind*uf,intx,inty){returnfind(uf,x)find(uf,y);}intmain(){intn5;UnionFind*ufcreateUnionFind(n);// 建立关系0-1, 2-3, 1-2unionSet(uf,0,1);unionSet(uf,2,3);unionSet(uf,1,2);printf(张三(0)和赵六(3)是否认识%s\n,isConnected(uf,0,3)?是:否);printf(张三(0)和孙七(4)是否认识%s\n,isConnected(uf,0,4)?是:否);free(uf-parent);free(uf-rank);free(uf);return0;}这段代码最关键的就是 find 函数中的那一行递归赋值操作它让查找路径上的每个节点都直接指向根节点从而保证后续查询几乎可以在常数时间内完成。与暴力算法的对比如果没有并查集我们通常会怎么解决这个问题呢大多数人可能会想到用链表或者数组存储每个人的直接朋友每次查询就从一个朋友列表跳到另一个朋友列表直到找到目标或者遍历完所有可能。想象一下这样的场景在一个有十万个用户的社交网络中有五十万条好友关系现在要进行十万次查询。如果用遍历的方法每次查询都可能要跳转很多次累计下来的计算量会让程序运行得很慢。而使用并查集除了最开始需要线性时间初始化之外后续的每次合并和查询操作都只需要极短的时间几乎是瞬间完成。当然并查集也有它的局限性它适合处理关系只增不减的情况。如果今天两人还是朋友明天又绝交了并查集就不好直接处理这种删除操作。实际应用场景并查集在实际开发中有很多巧妙的应用。比如在社交网络中判断两个用户是否属于同一个圈子或者合并两个群组都可以用它来实现。在图像处理中如果我们想识别一张照片中哪些像素点属于同一个物体可以用并查集来合并相邻的相似像素。一开始每个像素都是独立的如果相邻两个像素颜色相近就把它们合并到同一个集合中最后统计有多少个集合就知道有多少个物体。在网络连接问题中判断两台计算机是否可以通过网络互相通信也可以用并查集来维护连通状态。当建立新的网络连接时就是合并操作查询两台机器是否连通就是查找操作。总结并查集算法的精髓在于用树结构来维护集合关系通过路径压缩这个技巧几乎可以将单次查询的时间复杂度降到常数级别。它的代码实现简洁思路直观特别适合处理那些动态添加关系的连通性问题。理解并查集的关键在于明白那个 parent 数组背后的树形结构以及递归查找过程中路径压缩是如何将长链变短、让查询变快的。掌握了这个数据结构你就拥有了解决大规模关系查询问题的利器。
