并查集结构

简介: 并查集结构

并查集

增删改查时间复杂度为O(1)的结构目前学到的有哈希表跟并查集

什么是并查集?

1)有若干个样本a、b、c、d…类型假设是V

2)在并查集中一开始认为每个样本都在单独的集合里

3)用户可以在任何时候调用如下两个方法:

   boolean isSameSet(V x, V y):查询样本x和样本y是否属于一个集合

   void union(V x, V y) :把x和y各自所在集合的所有样本合并成一个集合

4)isSameSet和union方法的代价越低越好,最好是O(1)

补充

1)每个节点都有一条往上指的指针

2)节点a往上找到的头节点,叫做a所在集合的代表节点

3)查询x和y是否属于同一个集合,就是看看找到的代表节点是不是一个

4)把x和y各自所在集合的所有点合并成一个集合,只需要小集合的代表点挂

在大集合的代表点的下方即可

并查集的优化

1)节点往上找代表点的过程,把沿途的链变成扁平的

2)小集合挂在大集合的下面

3)如果方法调用很频繁,那么单次调用的代价为O(1),两个方法都如此

并查集的应用

   解决两大块区域的合并问题

   常用在图等领域中

核心代码&&详细注释

package com.harrison.class10;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;
public class Code01_UnionFind {
  // 自定义V类型,每个样本value外面包裹一层
  public static class Node<V>{
    V value;
    public Node(V v) {
      value=v;
    }
  }
  public static class UnionSet<V>{
    // 在nodes表里面,任何一个样本value都一一对应一个结点
    // 且初始化以后,永远不会有改动,只是记下对应关系
    public HashMap<V, Node<V>> nodes;
    // 每一个结点和自己的父结点都一一对应,记录在parents表里面
    public HashMap<Node<V>, Node<V>> parents;
    // 只有一个点,且这个点是集合的代表点
    public HashMap<Node<V>, Integer> sizeMap;
    public UnionSet(List<V> values) {// 用户把所有样本一次性给出
      for(V cur:values) {
        // 将每一个样本value都在外面包裹一层形成node
        Node<V> node=new Node<>(cur);
        // 记下对应关系,之后永不改变
        nodes.put(cur, node);
        // 因为一开始每一个样本只有自己,所以父结点仍然是自己
        parents.put(node, node);
        // 因为一开始每一个点都是代表点,所以集合大小就是1
        sizeMap.put(node, 1);
      }
    }
    // 从点cur开始,一直往上找,找到不能再往上的代表点,返回
    // 沿途所有结点都放入一个容器里(容器可以不是栈),目的是记下沿途路径
    public Node<V> findFather(Node<V> cur){
      Stack<Node<V>> path=new Stack<>();
      while(cur!=parents.get(cur)) {
        path.push(cur);
        cur=parents.get(cur);
      }
      // 跳出上面的循环后,cur一定指向代表点
      // 返回代表点之前,把沿途所有结点的父结点都改成代表点
      // 重要优化就体现在这,将链扁平化
      while(!path.isEmpty()) {
        parents.put(path.pop(), cur);
      }
      return cur;
    }
    public boolean isSameSet(V a,V b) {
      // 如果两个样本中有任何一个样本没有在nodes表里初始化,
      // 就必然不会在同一个集合里
      if(!nodes.containsKey(a) || !nodes.containsKey(b)) {
        return false;
      }
      // if没中,说明两个样本都在nodes表里登记了
      // 通过样本找它所在集合的代表点,如果两个代表点的内存地址一样
      // 就说明是在同一个集合
      return findFather(nodes.get(a))==findFather(nodes.get(b));
    }
    // 注意:是a样本所在的整个集合 和 b样本所在的整个集合 进行合并
    public void union(V a,V b) {
      // 没有登记,无法合并
      if(!nodes.containsKey(a) || !nodes.containsKey(b)) {
        return ;
      }
      // 登记了的话,找到自己所在集合的代表点
      Node<V> aHead=findFather(nodes.get(a));
      Node<V> bHead=findFather(nodes.get(b));
      // 只有两个代表点内存地址不一样才需要合并
      // 否则,说明这两个代表点所代表的两个集合本来就合并好了
      if(aHead!=bHead) {
        // 分别求得两个集合的的大小
        int aSetSize=sizeMap.get(aHead);
        int bSetSize=sizeMap.get(bHead);
        Node<V> big=aSetSize>=bSetSize?aHead:bHead;
        Node<V> small=big==aHead?bHead:aHead;
        // 小集合挂在大集合的下面
        // 直接把小集合头节点的父结点改为大集合的头节点
        parents.put(small, big);
        // 所以大集合的大小就变为两个集合大小相加
        sizeMap.put(big, aSetSize+bSetSize);
        // 小集合头节点不在作为代表点了,所以删掉在sizeMap里的记录
        sizeMap.remove(small);
      }
    }
  }
}

相关文章
|
2月前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
|
2月前
【数据结构】环形、相交、回文、分割、合并、反转链表
【数据结构】环形、相交、回文、分割、合并、反转链表
31 0
|
存储 机器学习/深度学习 人工智能
数据结构学习笔记——图的存储结构(邻接矩阵和邻接表)
数据结构学习笔记——图的存储结构(邻接矩阵和邻接表)
数据结构学习笔记——图的存储结构(邻接矩阵和邻接表)
|
7月前
|
算法 数据处理 Python
深入理解二叉树:结构、遍历和实现
深入理解二叉树:结构、遍历和实现
深入理解二叉树:结构、遍历和实现
|
7月前
|
存储 容器
图的存储结构之打印邻接表
图的存储结构之打印邻接表
剑指offer(C++)-JZ26:树的子结构(数据结构-树)
剑指offer(C++)-JZ26:树的子结构(数据结构-树)
|
存储 算法 编译器
探索二叉树:结构、遍历与应用
什么是二叉树? 二叉树是一种由节点组成的层次结构,其中每个节点最多有两个子节点,分别称为左子节点和右子节点。这种结构使得二叉树在存储和搜索数据时非常高效。二叉树的一个特殊情况是二叉搜索树(Binary Search Tree,BST),它满足左子节点的值小于父节点,右子节点的值大于父节点,这种特性使得在BST中进行查找操作更加高效。
109 0
【数据结构和算法思想】递归思想
在程序中可以调用函数来完成任务,为了完成相同的任务可以调用同一个函数。如果在函数中调用函数本身,那么改函数就被称为递归函数。递归函数的调用是按层,不是次,有 N 层就同时调用(打开)了 N 个函数,不是 N 次。 无限递归(递而不归、死递归),栈溢出(函数的调用有时间和空间的开销,一个程序中同时调用的函数个数是有限的)。• 递归函数的调用有时间和空间的开销,而且递归的次数受到堆栈大小的限制。 • 循环没有函数调用和返回中的参数传递和返回值的额外开销,更快。 如何在递归和循环之间选择? 一般情况下,当循环方法比较容易实现时,应该避免使用递归。当很难简历一个循环方法时,递归可能是一个很好的选择
数据结构193-图论-图的遍历方法
数据结构193-图论-图的遍历方法
72 0
数据结构193-图论-图的遍历方法
数据结构199-图论-深度优先遍历实现
数据结构199-图论-深度优先遍历实现
69 0
数据结构199-图论-深度优先遍历实现