并查集的创建

通常在解题过程中会遇到一种问题,这种问题会给出一个List集合,里面包含n个V类型的数,我们在接收到这个list之后,要把它里面的所有数据先包装成一个节点,然后每一个节点都是一个单独的集合,这样在初始阶段一共就有n个集合。我们把n个单独的集合通过一定的方法合并在一起,以实现高效查找元素的过程。而这样一个通过特定方法组合而成的集合就称之为并查集。

首先,创建出一个节点类。这个节点类可以看作是一个包装过程,目的是将传进来的数据包装成一个节点,后面在并查集中,会对这些包装后的节点进行操作。

// Node structure
public static class Node<V>{
	V value;
	
	public Node(V value){
		this.value=value;
	}
}

然后,创建出一个并查集结构。这个并查集提供了以下几种方法:查找某一个数所在集合的根节点(findAncestor)、两个数是否位于同一个集合(isSameSet)、合并两个集合(union)以及查看当前并查集中的集合数量(sets)。

// UnionFind structure
public static class UnionFind{
	// 创建一个nodes表,key为当前V类型的数,value为将这个数包装之后形成的节点
	HashMap<V, Node<V>> nodes;
	// fathers表,key表示当前节点,vlaue表示当前节点的父节点
	HashMap<Node<V>, Node<V>> fathers;
	// sizeMap表,key为当前节点,value为当前节点所在集合共有多少个节点
	// 这里key通常为某一个集合的代表节点也就是头节点
	HashMap<Node<V>, Integer> sizeMap;

	// 初始化并查集
	public UnionFide(List<V> values){
		nodes = new HashMap<>();
		parents = new HashMap<>();
		sizeMap = new HashMap<>();
		fro(V cur : values){
			// 初始时刻将传进来的所有V类型的数包装成一个节点
			Node<V> node = new Node<>(cur);
			// 将当前数和包装后的节点放入nodes表中
			nodes.put(cur, node);
			// 将当前节点和它的父节点放入fathers表中,初始时刻设置其父节点为自己
			fathers.put(node, node);
			// 将当前节点为头的集合中节点的数量设为1,因为此时每个V类型的数形成的节点单独为一个集合
			sizeMap.put(node, 1);
		}
	}
	
	// findAncestor方法用于找到当前节点所在集合的最头部节点,也就是当前节点在该集合里的老祖宗
	public Node<V> findAncestor(Node<V> cur){
		// 搞一个栈path,当cur节点往上找根祖先的时候,把它沿途的祖先们都压进栈里,至于压栈的作用后面会进行说明
		Stack<Node<V>> path = new Stack();
		// 只有当某个节点的父节点是它自己,才意味着它是自己集合中的根节点
		// 当然,一开始的时候每个集合中只有一个节点,那么每个节点都是本集合中的根节点
		while(cur != parents.get(cur)){
			stack.push(cur); // 如果没有找到根,就把当前这个节点压栈
			cur = parents.get(cur); // 然后让当前节点来到它的父结点位置,一直循环往上找
		}
		// 当程序跳出上一个while循环来到这里,就意味着当前节点cur来到了集合的根节点位置
		while(!stack.isEmpty()){
			// 这里我们就能知道刚刚压栈是做什么用的了
			// 如果栈不为空,就依次弹出节点,并把这些节点的父节点设置成刚刚找到的根节点
			// 这些依次弹出的节点,就是最初的cur节点往上找根的祖先们
			// 本来它们是以父子的形式找了很长的路才找到根,也就是说这棵树的高度比较高
			// 现在,把沿途所有节点的父亲全部设为根节点,这样一来,相当于原来是串起来的高树,现在变成并行的两层树了
			// 沿途所有具有父子关系的节点现在都有一个共同的父亲,那就是根节点
			parents.put(stack.pop(), cur);
		}
		// 这件事就叫做路径压缩,目的是当后面再去查找沿途这些节点的根节点时,就能以O(1)的时间复杂度找到
		// 做完路径压缩,把刚刚找到的根节点返回就行了
		return cur;
	}
	 
	// isSameSet方法用于判断两个V类型的数所形成的节点是否在同一个集合中
	public boolean isSameSet(V a, V b){
		// 直接返回这两个节点往上找到的根节点是否相同即可,因为一个集合中只有一个根节点
		return findAncestor(nodes.get(a)) == findAncestor(nodes.get(b));
	}
	
	// union方法用于将两个数所在的集合合并成一个大的集合
	// 合并规则为:小集合挂在大集合的下面
	public void union(V a, V b){
		// 先看两个数是否在同一集合中,如果不是,就找到各自的根节点,并比较哪个集合的size大,size小的集合挂在size大的集合下面
		Node<V> aHead = findAncestor(nodes.get(a));
		Node<V> bHead = findAncestor(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);
			// 调整大集合的size为大小集合的size之和
			sizeMap.put(big, aSetSize + bSetSize);
			// 删除小集合的size信息
			sizeMap.remove(small);
		}
	}
	
	// sets方法用于返回当前并查集中有多少个集合,直接返回sizeMap表的大小即可
	public int sets(){
		return sizeMap.size();
	}
}
上一篇:组织树筛选符合条件数据


下一篇:LeetCode-102-二叉树的层序遍历