這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)?lái)有關(guān)Java中怎么利用HashMap實(shí)現(xiàn)并查集，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

成都創(chuàng)新互聯(lián)服務(wù)項(xiàng)目包括田家庵網(wǎng)站建設(shè)、田家庵網(wǎng)站制作、田家庵網(wǎng)頁(yè)制作以及田家庵網(wǎng)絡(luò)營(yíng)銷策劃等。多年來(lái)，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，田家庵網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到田家庵省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

并查集的定義：

并查集，在一些有N個(gè)元素的集合應(yīng)用問(wèn)題中，我們通常是在開(kāi)始時(shí)讓每個(gè)元素構(gòu)成一個(gè)單元素的集合，然后按一定順序?qū)儆谕唤M的元素所在的集合合并，其間要反復(fù)查找一個(gè)元素在哪個(gè)集合中。這一類問(wèn)題近幾年來(lái)反復(fù)出現(xiàn)在信息學(xué)的國(guó)際國(guó)內(nèi)賽題中，其特點(diǎn)是看似并不復(fù)雜，但數(shù)據(jù)量極大，若用正常的數(shù)據(jù)結(jié)構(gòu)來(lái)描述的話，往往在空間上過(guò)大，計(jì)算機(jī)無(wú)法承受;即使在空間上勉強(qiáng)通過(guò)，運(yùn)行的時(shí)間復(fù)雜度也極高，根本就不可能在比賽規(guī)定的運(yùn)行時(shí)間(1~3秒)內(nèi)計(jì)算出試題需要的結(jié)果，只能用并查集來(lái)描述。并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合(Disjoint Sets)的合并及查詢問(wèn)題。常常在使用中以森林來(lái)表示。

并查集的功能：

1、找到某個(gè)節(jié)點(diǎn)的頭節(jié)點(diǎn)2、查詢兩個(gè)節(jié)點(diǎn)是否在同一個(gè)集合里3、合并兩個(gè)集合

并查集的Java實(shí)現(xiàn)：

public static class Node { // Node可以是任意的類型 int， String等等 } public static class UnionFind { public HashMap fatherMap; // 用來(lái)存放每個(gè)節(jié)點(diǎn)的頭節(jié)點(diǎn) public HashMap sizeMap; // 用來(lái)保存每個(gè)集合的大小 public UnionFind() {  fatherMap = new HashMap();  sizeMap = new HashMap(); } public void makeSet(List nodes) {  fatherMap.clear();  sizeMap.clear();  for (Node node : nodes) {  fatherMap.put(node, node); // 每個(gè)節(jié)點(diǎn)單獨(dú)成為一個(gè)集合，頭節(jié)點(diǎn)指向自己  sizeMap.put(node, 1); // 初始化時(shí)每個(gè)集合的大小為1  } } private Node findHead(Node node) {  Node father = fatherMap.get(node);  while (father != node) {  father = findHead(father); // 遞歸向上找  }  fatherMap.put(node, father); // 每次遞歸時(shí)都把每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)直接指向頭節(jié)點(diǎn)  return father; } public boolean isSameSet(Node aNode, Node bNode) {  return findHead(aNode) == findHead(bNode); } public void union(Node aNode, Node bNode) {  if (aNode == null || bNode == null) {  return;  }  Node aHead = findHead(aNode);  Node bHead = findHead(bNode);  if (aHead != bHead) {  int aSize = sizeMap.get(aHead);  int bSize = 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);  }  } } }

上述就是小編為大家分享的Java中怎么利用HashMap實(shí)現(xiàn)并查集了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

文章標(biāo)題：Java中怎么利用HashMap實(shí)現(xiàn)并查集-創(chuàng)新互聯(lián)
文章位置：http://weahome.cn/article/dcejjh.html