并查集是一种十分好用的树形数据结构,用来合并2棵树

并查集原理 :就是每次给定2个节点,然后通过找他的父亲节点,直到找到根节点,如果2个节点的根节点不是同一个,则说明这2个节点不在同一个树上,则合并2棵树
并查集应用一般可以判断图中存不存在环
最小生成树Kurskal算法(克鲁斯卡尔算法)也是运用并查集来实现的.(有兴趣的可以下去自己学学看),这里不做详细说明
对最小生成树感兴趣的可以查看我的另外一篇博客----- 最小生成树prim算法和kruskal算法

并查集实现可以分为寻找根和合并根2部分来实现
具体实现

//这里是判断一个图中存不存在环
 * @author Bhg
 * @date 2020/3/22
public class Demo1 {
    static int parent[];
    //初始化
    private static void initialize(int[] parent) {
        for (int i = 0; i < parent.length; i++) {
            parent[i]=-1;
    public static void main(String[]args){
        parent=new int[6];
        initialize(parent);
        int [][]set={{0,1},{1,2},{1,3},{3,4},{2,5}};
        for (int i = 0; i < set.length; i++) {
            int x=set[i][0];
            int y=set[i][1];
            if (union_root(x,y)==0){
                System.out.println("存在环");
                return;
        System.out.println("不存在环");
    //寻找一个点的根节点
    private static int find_root(int x) {
        int x_root=x;
        while (parent[x_root]!=-1){
            x_root=parent[x_root];
        return x_root;
    private static int union_root(int x,int y) {
        int  x_root=find_root(x);
        int  y_root=find_root(y);
        if (x_root==y_root){
            return 0;
        }else {
            parent[x_root]=y_root;
            return 1;
代码完成后,我们发现,在寻找根节点的时候,有可能这棵树的深度很深,那么查询的效率就会很低,如何优化呢?
 首先我们要明白为什么会效率低,是因为树的深度太大,那么就想办法降低树的深度,有两个办法
 
1,按秩合并
 
如图所示
 
 如图合并这2个树有2种方法
 
 可以看到,第一棵树深度为5, 第二棵树深度为4
 如果深度较小的树作为根,则树的深度会增加1,但是如果深度较大的树作为根,则深度不变
 这就是按秩合并,每次合并前判断一下深度,则需要一个数组rank来记录当前树的深度
 
代码实现:
 
private static void union_root(int x, int y) {
        int x_root = find_root(x);
        int y_root = find_root(y);
        //如果根节点相同,则不做任何操作
        if (x_root == y_root) {
            return;
        } else {
            //合并的时候加以判断,向根深的一边合并
            if (rank[x_root]>rank[y_root]){
                parent[y_root]=x_root;
            }else if(rank[x_root]<rank[y_root]){
                parent[x_root]=y_root;
            }else {
                parent[y_root]=x_root;
                //如果2个树深度一样,则rank+1
                rank[x_root]++;
            //parent[x_root] = y_root;
这样优化树的深度还是没有达到很我们预期的效果,
 如果在寻找根的时候,让所有的子节点全部都直接指向根节点,这样每次查询根节点就能直接去寻找根节点,也就是O(1)的时间复杂度.
 这就是路径压缩.
 
2,路径压缩
 
如图所示
 
 第二个图,直接让所有的节点都直接连着根
 如何实现呢?
 具体实现,就是在寻找根节点的时候,找到根节点,然后记录根节点,
 再重新找该节点的父节点,如果父节点不是根节点,则直接让它指向根节点,直到找到根节点为止,具体看代码理解
 
代码实现:有两种方式
 
递归(代码很简单,不好理解,如果实在不能理解,就直接拿着用吧)
 
private static int find_Node(int x) {
        if (parent[x] == -1) return x;
        return parent[x] =find_Node(parent[x]);
非递归(代码比较好理解)
 
//非递归
private static int find_Node(int x) {
        int root = x;
        while (parent[root] != -1){
            root = parent[root];
        int temp = root; //记录祖先节点
        while (parent[x] != -1){
            int r = parent[x];
            parent[x] = temp;
            x = r;
        return root;
熟练掌握还是要自己练
 
此处附上例题
 
蓝桥杯:合根植物
 模板题
 蓝桥杯:村庄建设---------此题是最小生成树,可以练习练习,当然也可以用prim算法,此处不做详解
                    并查集并查集是一种十分好用的树形数据结构,用来合并2棵树并查集原理:就是每次给定2个节点,然后通过找他的父亲节点,直到找到根节点,如果2个节点的根节点不是同一个,则说明这2个节点不在同一个树上,则合并2棵树并查集应用一般可以判断图中存不存在环最小生成树Kurskal算法(克鲁斯卡尔算法)也是运用并查集来实现的.(有兴趣的可以下去自己学学看),这里不做详细说明.并查集实现可以分为寻找根和合...
				
  今天学习一种新的数据结构并查集。“并”表示合并，“查”表示查找，“集”表示集合。其基本思想是用 father[i] 表示元素 i 的父节点。例如 father[1] = 2 表示元素 1 的父节点是 2。如果 father[i] = i，那么说明 i 是根节点，根节点作为一个集合的标识，如下图表示两个集合，它们的根节点分别是 1 和 5。当然，如果不使用数组来记录，而使用 map 来记录，那么可以使用 father.get(i) = null 来表示根节点。
1.并查集的基本操作
下面定义了并查集的类
 维护一个森林，每一棵树都代表一个集合，树根元素为这个集合的代表元。利用数组father[]查询记录每个元素的父亲节点。
查询一个元素所处集合时，只需不断寻找父节点，即可找到该元素所处集合的代表元。
合并两个集合时，先找到两个集合代表元x,y,然后令father[x]=y即可。
 路径压缩，沿着树根的路径找到元素a所在集合代表元b后，对这条路径上的所有元素x，令father[a]=b;
				
并查集就是将原本不在一个集合里面的内容合并到一个集合中。在实际的场景中用处不多。​
除了出现在你需要同时去几个集合里面查询，避免出现查询很多次，从而放在一起查询的情况。​
下面简单实现一个例子，我们来举例说明一下什么是并查集，以及究竟并查集解决了什么问题。​
package com.chaojilaji.book.andcheck;
public class AndCheckSet {
    public static Integer getFather(int[] father, in
				
文章目录并查集简易并查集图解简易代码实现并查集优化图解并查集优化代码实现
定义:  并查集是一种树型数据结构(多叉树)，并查集可以高效地查找和合并，常用于求连通问题，最小生成树kruskal算法
简易并查集
每个数据可以看作一个节点
每一组数据都是一颗树
一个组中的数据对应的树和另外一个组中数据对应的树之间没有任何关系
初始化的时候把索引当作每个组的标识符
--------------测试并查集中组的数量:--------------
				
并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。并查集跟树有些类似，只不过她跟树是相反的。在树这个数据结构里面，每个节点会记录它的子节点。在并查集里，每个节点会记录它的父节点【1】。
并查集的精髓在于，两块集合(区域)有没有相交，以及要不要联通两块区域(集合)。参考树的结构，把元素挂到父节点下，若两个元素的父节点相同，则是同一块区域，两个元素的父节点不相同，则不是同一块区域。
				
并查集是一种常用的数据结构，用于解决联通性问题，通常应用于图论中。以下是一个使用Java实现并查集的示例。
假设我们有一个由10个节点构成的图，节点编号分别为0-9。现在我们需要将这10个节点分成3个集合，其中第一个集合包括节点0,1,2,第二个集合包括节点3,4,5,第三个集合包括节点6,7,8,9。我们可以使用并查集来实现这个目标。
下面是使用Java实现并查集的示例代码：
```java
public class UnionFind {
    int[] parent;
    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
    public int find(int x) {
        if (parent[x] == x) {
            return x;
        return parent[x] = find(parent[x]);
    public void union(int x, int y) {
        int px = find(x);
        int py = find(y);
        parent[px] = py;
    public static void main(String[] args) {
        UnionFind uf = new UnionFind(10);
        uf.union(0, 1);
        uf.union(1, 2);
        uf.union(3, 4);
        uf.union(4, 5);
        uf.union(6, 7);
        uf.union(7, 8);
        uf.union(8, 9);
        System.out.println(uf.find(0) == uf.find(2));
        System.out.println(uf.find(3) == uf.find(5));
        System.out.println(uf.find(6) == uf.find(9));
这个示例中，我们首先创建一个长度为10的并查集，表示有10个节点。然后我们调用`union()`方法将节点分成3个集合。最后，我们可以使用`find()`方法查询两个节点是否在同一个集合中。
运行这个示例代码，可以看到输出结果为：
这说明节点0、1、2在同一个集合中，节点3、4、5在同一个集合中，节点6、7、8、9在同一个集合中，符合我们的预期。