Java中怎么利用HashMap實現(xiàn)并查集

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

創(chuàng)新互聯(lián)專注于企業(yè)全網(wǎng)營銷推廣、網(wǎng)站重做改版、鹿邑網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、成都h5網(wǎng)站建設(shè)、成都商城網(wǎng)站開發(fā)、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站制作、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為鹿邑等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

并查集的定義：

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

并查集的功能：

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

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

public static class Node { // Node可以是任意的類型 int， String等等 } public static class UnionFind { public HashMap<Node, Node> fatherMap; // 用來存放每個節(jié)點的頭節(jié)點 public HashMap<Node, Integer> sizeMap; // 用來保存每個集合的大小 public UnionFind() {  fatherMap = new HashMap<Node, Node>();  sizeMap = new HashMap<Node, Integer>(); } public void makeSet(List<Node> nodes) {  fatherMap.clear();  sizeMap.clear();  for (Node node : nodes) {  fatherMap.put(node, node); // 每個節(jié)點單獨成為一個集合，頭節(jié)點指向自己  sizeMap.put(node, 1); // 初始化時每個集合的大小為1  } } private Node findHead(Node node) {  Node father = fatherMap.get(node);  while (father != node) {  father = findHead(father); // 遞歸向上找  }  fatherMap.put(node, father); // 每次遞歸時都把每個節(jié)點的父節(jié)點直接指向頭節(jié)點  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實現(xiàn)并查集了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

網(wǎng)頁標(biāo)題：Java中怎么利用HashMap實現(xiàn)并查集
當(dāng)前鏈接：http://muchs.cn/article18/ghiddp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)頁設(shè)計公司、移動網(wǎng)站建設(shè)、建站公司、營銷型網(wǎng)站建設(shè)、App開發(fā)、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)