Java使用HashMap实现并查集
并查集的定义:
并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。
并查集是一种树型的数据结构,用于处理一些不相交集合(DisjointSets)的合并及查询问题。常常在使用中以森林来表示。
并查集的功能:
1、找到某个节点的头节点
2、查询两个节点是否在同一个集合里
3、合并两个集合
并查集的Java实现:
publicstaticclassNode{ //Node可以是任意的类型int,String等等 } publicstaticclassUnionFind{ publicHashMapfatherMap;//用来存放每个节点的头节点 publicHashMap sizeMap;//用来保存每个集合的大小 publicUnionFind(){ fatherMap=newHashMap (); sizeMap=newHashMap (); } publicvoidmakeSet(List nodes){ fatherMap.clear(); sizeMap.clear(); for(Nodenode:nodes){ fatherMap.put(node,node);//每个节点单独成为一个集合,头节点指向自己 sizeMap.put(node,1);//初始化时每个集合的大小为1 } } privateNodefindHead(Nodenode){ Nodefather=fatherMap.get(node); while(father!=node){ father=findHead(father);//递归向上找 } fatherMap.put(node,father);//每次递归时都把每个节点的父节点直接指向头节点 returnfather; } publicbooleanisSameSet(NodeaNode,NodebNode){ returnfindHead(aNode)==findHead(bNode); } publicvoidunion(NodeaNode,NodebNode){ if(aNode==null||bNode==null){ return; } NodeaHead=findHead(aNode); NodebHead=findHead(bNode); if(aHead!=bHead){ intaSize=sizeMap.get(aHead); intbSize=sizeMap.get(bHead); if(aSize<=bSize){ fatherMap.put(aHead,bHead); sizeMap.put(bHead,aSize+bSize); }else{ fatherMap.put(bHead,aHead); sizeMap.put(aHead,aSize+bSize); } } } }
才疏学浅,如有错误希望大家多多指出,一定虚心接受。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。