数据结构-并查集

- # 并查集

• 定义:并查集是一种用于维护一系列不相交集合的数据结构，每个集合可以看作一棵树，树中的节点代表元素，节点间的边表示元素之间的父子关系。
• 并查集的核心操作
  • 查找:确定一个元素所在的集合标识（通常是树的根节点），即确定元素所属的“连通分量”
  • 合并:将两个元素所在的不同集合合并成一个集合，即将两棵树合并为一棵树。
• 代码实现

  public class UnionSetDemo {
      //parent数组用于存储每个元素的父节点，初始化时每个元素的父节点为其自身。
      private int[] parent;
      //rank数组用于存储每个根节点的高度，初始化时每个根节点的高度为1。
      private int[] rank;
  
      public UnionSetDemo(int n) {
          parent = new int[n];
          rank = new int[n];
          //初始化每个元素为独立的集合,父节点为自己,秩为1
          for (int i=0;i<n;i++){
              parent[i]=i;
              rank[i]=1;
          }
      }
      //查找操作
      public int find(int x){
          //若x的父节点不是自己,说明x不是根节点,将当前节点赋为父节点后,再进行递归处理;
          if (parent[x]!=x){
              parent[x]=find(parent[x]);
          }
          return parent[x];
      }
      //合并操作
      public void union(int x,int y){
          //找到x和y的根节点
          int rootX=find(x);
          int rootY = find(y);
          if (rootX==rootY){
              //已经在同一集合中无需合并
              return;
          }
          //按照高度合并,将秩较小的树接到秩较大的树下
          if (rank[rootX]<rank[rootY]){
              //将rootX的父节点设为rootY
              parent[rootX]=rootY;
          }else if (rank[rootX]>rank[rootY]){
              //将rootY的父节点设为rootX
              parent[rootY]=rootX;
          }else {
              //若高度相同,任选一个座位父节点,并将其高度+1
              parent[rootY]=rootX;
              rank[rootX]++;
          }
      }
  }
  

• 应用场景
  • 图论计算
    1.最小生成树：在 Kruskal’s algorithm 中，用于检测新加入边的两个端点是否已属于同一连通分量，如果不是，则加入该边并合并相应的集合。
    2.连通分量：计算无向图中连通分量的数量，或者找出所有连通分量的具体构成。
  • 数据一致性维护
    1.分布式系统：在分布式环境中，多个节点可能持有数据的局部视图。并查集可以用于维护全局一致性的数据分区视图，如跟踪节点间的连接状态，确保节点间通信的一致性。
    2.多线程同步：在多线程环境下，通过并查集可以实现轻量级锁或资源池的管理，确保线程对共享资源的访问遵循一定的同步规则。
  • 网络流与图算法
    1.缩点：在网络流算法中，通过并查集将属于同一连通分量的节点缩为一个超级节点，简化图结构，加速算法运行。
    2.稀疏图操作：在稀疏图的各种操作中，如查找两点间最短路径、判断是否存在环等，可以先使用并查集预处理，合并相关节点，简化问题规模。
  • 字符串处理
    1.子串匹配：在某些字符串匹配算法中，利用并查集记录子串之间的关联关系，快速判断两个子串是否属于同一“家族”。